title: Given a node, how long will it take to burn the whole binary tree?
body: <p>I got a problem during one of my mock interview where I had to find how long will a binary tree completely burn down after one given node is already on fire.</p>
  
  <blockquote>
    <p><em>"A binary tree is started burning from a leaf node. What is the
    time(1second to burn from node to node) it takes to entire tree get
    burned? The fire will spread to all the paths from a node.</em>"</p>
  </blockquote>
  
  <p>Say you have a tree like this, where N is the node that is on fire. This is
    happening in the first second, where seconds is s, so in the zeroth s:</p>
  
  <pre><code>           1
         /       \
        1          1
      /  \          \
     1    1          1
        /   \         \
       1     N         1
                        \
                         1
  </code></pre>
  
  <p>After one second has passed, the tree will be updated with more burned nodes.
    An example of the next second (s + 1) will be like this:</p>
  
  <pre><code>           1
         /       \
        1          1
      /  \          \
     1    N          1
        /   \         \
       1     N         1
                        \
                         1
  </code></pre>
  
  <p>An example of the next second (s + 2) will be like this:</p>
  
  <pre><code>           1
         /       \
        N          1
      /  \          \
     1    N          1
        /   \         \
       N     N         1
                        \
                         1  
  </code></pre>
  
  <p>Now at the third second (s + 3) will be like this:</p>
  
  <pre><code>           N
         /       \
        N          1
      /  \          \
     N    N          1
        /   \         \
       N     N         1
                        \
                         1
  </code></pre>
  
  <p>With the same pattern, the tree will be burned in (s + 7)</p>
  
  <pre><code>           N
         /       \
        N          N
      /  \          \
     N    N          N
        /   \         \
       N     N         N
                        \
                         N
  </code></pre>
  
  <p>After understanding a little bit, I did a small research in figuring out how to do it. I found this cool <a href="http://techieme.in/tree-diameter/" rel="nofollow noreferrer">article</a> and followed it up and implement the idea behind.</p>
  
  <p>My approach was to find the diameter, along with the height of the tree to look for the furthest node to node. However, when I implemented my functions, I'm only getting the result of the <strong>starting node</strong> to the end of the <strong>given node</strong> without checking the previous parent nodes. Here is my implementation in Python 3:</p>
  
  <pre><code># Tree class
  class Node:
      def __init__(self, key):
          self.left = None
          self.right = None
          self.value = key
  
  # Maximum height of a tree
  def maxHeight(root):
      if root is None:
          return 0
      else:
          return 1 + max(maxHeight(root.left), maxHeight(root.right))
  
  # Diameter of the tree
  def maxDiameter(root):
      how_long = 0
      if root is None:
          return 0
      else:
          root_diameter = maxHeight(root.left) + maxHeight(root.right)
  
          left_diameter = maxDiameter(root.left)
          right_diameter = maxDiameter(root.right)
          how_long = max(max(left_diameter, right_diameter), root_diameter)
          return how_long
  
  # Sample code
  root = Node(1)
  root.left = Node(1)
  root.right = Node(1)
  root.left.left = Node(1)
  root.left.right = Node(1)
  root.left.right.left = Node(1)
  root.left.right.right = Node(1)
  root.right.right = Node(1)
  root.right.right.right = Node(1)
  root.right.right.right.right = Node(1)
  print ("Starting from the given node, it will take %ds to burn the whole tree" % (maxDiameter(root.left.right)))
  </code></pre>
  
  <p>The expected output for this example should be 6s (starting from the 0s with the given node). But again, I'm not getting the full scope of the tree. From my own understanding, it has to work with all cases. So, what search would be helpful here, DFS or 
  BFS? I think having this in mind will guide me towards my solution, but again. Any feedback is appreciated :)</p>