Approach #1: Depth-First Search [Accepted]

Intuition

Any path can be written as two arrows (in different directions) from some node, where an arrow is a path that starts at some node and only travels down to child nodes.

If we knew the maximum length arrows L, R for each child, then the best path touches L + R + 1 nodes.

Algorithm

Let's calculate the depth of a node in the usual way: max(depth of node.left, depth of node.right) + 1. While we do, a path "through" this node uses 1 + (depth of node.left) + (depth of node.right) nodes. Let's search each node and remember the highest number of nodes used in some path. The desired length is 1 minus this number.

Complexity Analysis

• Time Complexity: . We visit every node once.

• Space Complexity: , the size of our implicit call stack during our depth-first search.

Analysis written by: @awice.