Sum of Root To Leaf Binary Numbers - Video Solutions

Problem Overview: Each root-to-leaf path in the binary tree represents a binary number where every node contributes a bit (0 or 1). Moving from the root to a leaf builds a binary sequence. Convert each path into its decimal value and return the sum of all such numbers.

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

This approach traverses the tree using recursion. As you move down a path, maintain the current binary value formed so far. At each node, shift the accumulated value left by one bit (current << 1) and add the node’s value using a bitwise OR or addition. When a leaf node is reached, the accumulated value represents a full binary number, so add it to the total sum.

The key insight: binary digits are built incrementally as you traverse the path. Shifting left is equivalent to multiplying by 2, which matches how binary numbers grow when a new bit is appended. Every node is processed exactly once, making the time complexity O(n) where n is the number of nodes. Recursion depth depends on the tree height, so space complexity is O(h). This method naturally fits problems involving path-based computations in tree structures and is the cleanest implementation using Depth-First Search.

Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))

The iterative version replaces recursion with an explicit stack. Each stack entry stores a pair: the current node and the binary value built along the path to that node. Pop a node from the stack, update the binary value using the same shift operation (value = (value << 1) | node.val), and check whether it is a leaf. If it is, add the value to the total sum. Otherwise, push its children onto the stack with the updated value.

This approach performs the same logical steps as recursive DFS but avoids relying on the call stack. It is useful in environments where recursion depth might be limited or when you want explicit control over traversal order. Time complexity remains O(n) since each node is visited once, and the stack holds at most O(h) nodes at a time in a balanced binary tree.

Recommended for interviews: Recursive DFS is typically expected because the code is concise and directly mirrors the tree structure. Interviewers look for the insight that the path forms a binary number and can be built incrementally using a left shift operation. Implementing the iterative stack version demonstrates deeper understanding of DFS mechanics and control over recursion.