Approach #1: Depth-First Search [Accepted]
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.
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.
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.