Insufficient Nodes in Root to Leaf Paths - Video Solutions

Problem Overview: You are given a binary tree and a limit value. A node is considered insufficient if every root-to-leaf path passing through it has a sum strictly less than the limit. Your task is to remove all such nodes and return the remaining tree.

This is a classic pruning problem on a tree. The key challenge is determining whether a node belongs to at least one valid root‑to‑leaf path whose sum is greater than or equal to the limit.

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

The most natural solution uses a recursive depth-first search. Traverse the tree from the root while maintaining the cumulative path sum. When you reach a leaf node, check whether the total sum is less than the limit. If it is, that leaf is insufficient and should be removed. During the recursion unwind, if both children of a node become null, the current node also becomes insufficient and must be pruned. This bottom‑up pruning ensures that nodes remain only if they lead to a valid root‑to‑leaf path.

The algorithm touches each node exactly once. The recursion depth is proportional to the height of the tree, giving O(n) time and O(h) space complexity. This approach is concise and aligns well with the recursive structure of a binary tree. Most interview solutions follow this pattern.

Approach 2: Iterative DFS Using Stack (Time: O(n), Space: O(n))

An iterative alternative simulates DFS using an explicit stack. Each stack entry stores the current node, the accumulated path sum, and references needed to update the parent. As you process nodes, push children with updated sums. When reaching leaves, determine whether the path satisfies the limit. If not, mark the node for removal and update its parent accordingly.

This method avoids recursion and may be useful in environments where recursion depth is limited. However, the bookkeeping is more complex because you must track parent-child relationships and update pointers after determining whether a subtree is valid. The time complexity remains O(n) since each node is processed once, while space can grow to O(n) in the worst case due to the explicit stack.

Recommended for interviews: The recursive DFS pruning approach. Interviewers expect you to recognize that insufficient nodes can only be determined after exploring all root‑to‑leaf paths below them. Demonstrating a clean post‑order DFS that removes children first and then evaluates the current node shows strong understanding of tree recursion.