Binary Tree Paths - Solution & Explanation

Problem Overview: Given the root of a binary tree, return every path from the root node to each leaf node. Each path must be represented as a string in the format node1->node2->node3. A leaf node is a node with no children, so a valid path ends only when both left and right pointers are null.

Approach 1: Depth-First Search (DFS) - Recursive (O(n) time, O(h) space)

The most natural way to solve this problem is with recursive Depth-First Search. Start from the root and carry the current path as a string while traversing the tree. At each node, append its value to the path. When you reach a leaf node, store the completed path in the result list. The recursion then backtracks and explores the remaining branches.

This approach works because DFS naturally explores one root-to-leaf path at a time. The recursion stack keeps track of the traversal state while you build the path incrementally. Each node is visited exactly once, giving a time complexity of O(n), where n is the number of nodes. The space complexity is O(h) due to the recursion stack, where h is the height of the binary tree. In skewed trees this becomes O(n), while balanced trees keep it closer to O(log n). This solution is concise and commonly expected in interviews.

Approach 2: Iterative DFS using a Stack (O(n) time, O(h) space)

The same traversal can be implemented iteratively using an explicit stack instead of recursion. Each stack entry stores a pair: the current node and the path string built so far. Pop an element, extend the path with the current node's value, and push its children back onto the stack with updated paths.

When the algorithm pops a node that has no left or right child, the path represents a complete root-to-leaf sequence and gets added to the result list. This method mirrors recursive DFS but avoids relying on the call stack. It still visits each node once, so the time complexity remains O(n). The stack holds at most one branch of nodes at a time, giving a space complexity of O(h). Iterative DFS is useful when recursion depth might be large or when you want explicit control over traversal order.

Both methods rely on tree traversal fundamentals from tree algorithms and follow a path-building pattern often used in backtracking style problems where partial results grow as you move deeper in the structure.

Recommended for interviews: Recursive DFS is the approach most interviewers expect. It demonstrates clear understanding of tree traversal and keeps the code short and readable. Mentioning the iterative stack version shows deeper knowledge of how recursion translates to explicit data structures and how to avoid recursion limits.