Approach #1: DepthFirst 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 depthfirst search.
Analysis written by: @awice.