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

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.

This can be solved using a recursive function which returns the length of the path from the current node down to the starting node (or just the longest path to any leaf if the starting node isn't below it).

We can also have it return the longest path so far from the starting node, if found, which is simply the sum of the function called on both the left and right children (plus one, for the current node).

This is similar to the solution described by m69.

This runs in O(n) time since the function runs in constant time (if you exclude the recursive calls), and the function gets called at most three times for each node (for the node itself and for its left and right children, in the case of leaf nodes).

This will use O(height) space, since we're not storing anything apart from the function calls with their variables, and the maximum number of those we can have in memory at any given time is equal to the recursion depth (i.e. the height of the tree).

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

# returns a tuple (max = the longest path so far, dist = current path)
def _recurse(node, start):
    if node is None:
        return (None, 0)
    else:
        max_left, dist_left = _recurse(node.left, start)
        max_right, dist_right = _recurse(node.right, start)
        # this node is the starting node
        if node == start:
            return (0, 0)
        # the starting node is in left or right
        elif max_right is not None or max_left is not None:
            return (dist_right + dist_left + 1,
                    (dist_left if max_right is None else dist_right) + 1)
        # we haven't seen the starting node
        else:
            return (None, max(dist_left, dist_right) + 1)

def time_to_burn(root, start):
    return _recurse(root, start)[0]

Test:

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)

>>> time_to_burn(root, root.left.right.right)
7

Solution which works with non-leaf starting nodes

The basic idea is to have 3 return values for each node:

• max, which is the longest path from the starting node gotten so far (or None if we haven't seen the starting node yet).
• above, which is the number of nodes above the starting node (or None if we haven't seen the starting node yet).
• below, which is the longest path below the starting node (or just the longest path from the current node if we haven't seen the starting node yet).

Calculating above and below from the child subtrees is fairly straight-forward - see the code for details.

We can define the longest path max from the current node as the maximum of:

• The longest path going downwards from the starting node (which is just below)
• and the longest path which includes the current node, which will be the distance from the current node to the starting node plus the longest path in the subtree without the starting node (plus one).

Code: (replacing the _recurse function above)

# returns a tuple (max, above, below)
def _recurse(node, start):
    if node is None:
        return (None, None, 0)
    else:
        max_left, above_left, below_left = _recurse(node.left, start)
        max_right, above_right, below_right = _recurse(node.right, start)
        # this node is the starting node
        if node == start:
            below = max(below_left, below_right)
            return (below, 0, below)
        # the starting node is in left or right
        elif above_right is not None or above_left is not None:
            return (max((0 if above_right is None else above_right) + below_left,
                        (0 if above_left is None else above_left) + below_right) + 1,
                    (above_right if above_left is None else above_left) + 1,
                    below_right if above_left is None else below_left)
        # we haven't seen the starting node
        else:
            return (None, None, max(below_left, below_right) + 1)

>>> time_to_burn(root, root.left.right)
6