Binary Tree Paths - Video Solutions

Problem Overview: Given the root of a binary tree, return every root-to-leaf path as a string. Each path should list node values from the root to a leaf separated by "->". A node is considered a leaf when it has no left or right child.

Approach 1: Depth-First Search (DFS) - Recursive (Time: O(n * h), Space: O(h))

The natural way to explore root-to-leaf paths is a recursive depth-first search. Start from the root and keep building the current path string as you traverse deeper into the binary tree. At each node, append its value to the path. When you reach a leaf node (both children are null), push the completed path into the result list.

This approach works because DFS explores one path fully before backtracking, which aligns perfectly with root-to-leaf path construction. Each recursive call handles one node and passes the updated path string to its children. The time complexity is O(n * h) in the worst case due to repeated string concatenation, where n is the number of nodes and h is the tree height. The recursion stack requires O(h) space.

The pattern is closely related to backtracking problems where you build a partial solution and extend it along different branches. Recursive DFS is concise, easy to reason about, and commonly expected in interviews.

Approach 2: Iterative DFS using a Stack (Time: O(n * h), Space: O(n))

If recursion is not preferred, you can simulate the DFS traversal using an explicit stack. Each stack entry stores a pair: the current node and the path string built so far. Start by pushing the root with its value as the initial path.

During traversal, pop a node from the stack, check whether it is a leaf, and add the path to the result if it is. Otherwise, push its children back onto the stack with updated path strings. Typically you push the right child first so the left subtree gets processed earlier, preserving the natural DFS order.

This approach avoids recursion limits and gives you full control over traversal. However, the stack may grow larger than the recursion stack in skewed trees because it stores path strings alongside nodes. Time complexity remains O(n * h) due to string building, while space complexity can reach O(n) in the worst case.

Recommended for interviews: Recursive DFS is the most common and expected solution. It clearly demonstrates understanding of tree traversal and root-to-leaf path construction. Showing the iterative stack version can be useful if the interviewer asks how to avoid recursion or simulate DFS manually.