Given a node, how long will it take to burn the whole binary tree?

Question

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.

"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."

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:

           1
       /       \
      1          1
    /  \          \
   1    1          1
      /   \         \
     1     N         1
                      \
                       1

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:

           1
       /       \
      1          1
    /  \          \
   1    N          1
      /   \         \
     1     N         1
                      \
                       1

An example of the next second (s + 2) will be like this:

           1
       /       \
      N          1
    /  \          \
   1    N          1
      /   \         \
     N     N         1
                      \
                       1  

Now at the third second (s + 3) will be like this:

           N
       /       \
      N          1
    /  \          \
   N    N          1
      /   \         \
     N     N         1
                      \
                       1

With the same pattern, the tree will be burned in (s + 7)

           N
       /       \
      N          N
    /  \          \
   N    N          N
      /   \         \
     N     N         N
                      \
                       N

After understanding a little bit, I did a small research in figuring out how to do it. I found this cool article and followed it up and implement the idea behind.

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 starting node to the end of the given node without checking the previous parent nodes. Here is my implementation in Python 3:

# 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)))

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 :)

Answer 1

It occurs to me that you need the following:

1. Whether the starting node is left or right of the root.
2. The depth of the starting node (call it dStart).
3. The depth of the node furthest from the root on the starting node's branch (i.e. left or right of the root). We'll call that dSameSide
4. Depth of the lowest common ancestor of the starting node and the node identified in #3. (call it dCommonAncestor)
5. Depth of the lowest node on the opposite side of the tree, dOppositeSide.

You can obtain all that information from a single inorder traversal of the tree.

The number of steps it takes to get from the starting node to the deepest node on that side of the tree is (dSameSide - dCommonAncestor) + (dStart - dCommonAncestor).

The number of steps it takes to get from the starting node to the deepest node on the opposite side is (dStart + dOppositeSide).

And the number of steps it takes to burn the entire tree is the maximum of those two.

I'll leave the implementation to you. You'll probably find How to find the lowest common ancestor of two nodes in any binary tree? helpful.

Answer 2

For those wondering what happened with this post, The solution used was this:

LeafSide = []

class Node:
    """Tree class."""

    def __init__(self, key):
        """Declare values of a node."""
        self.left = None
        self.right = None
        self.value = key


def leafHeight(root, leaf):
    """Height of the leaf."""
    if root is None:
        return 0
    else:
        if root.left is leaf:
            aux = 1 + leafHeight(root.right, leaf)
            LeafSide.append(aux)
            return 1
        if root.right is leaf:
            aux = 1 + leafHeight(root.left, leaf)
            LeafSide.append(aux)
            return 1
        return 1 + max(leafHeight(root.left, leaf), leafHeight(root.right, leaf))


def timeBurn(root, leaf):
    """How long will it take to burn the the node to furthest node."""
    hl = leafHeight(root.left, leaf)
    hr = leafHeight(root.right, leaf)
    opposite_LeafSide = 1 + hl + hr
    return max(opposite_LeafSide, LeafSide[0])


if __name__ == '__main__':
    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" % (timeBurn(root, root.left.right)))

Time: O(n)

Space: O(n)

If you notice, each node has a value of 1. The value of the node does not matter for this problem. It is just representing some value in it. The reason I have one is to think of a second (1 second Node). Thanks to everyone who helped me. I enjoyed reading all of the comments and approaches you guys were talking :). If you have a better idea in how to improve the code, feel free to comment below!