Path Sum

🎯

Path Sum

easyTREEAmazonMicrosoftFacebook

Imagine you are navigating a decision tree where each path represents a series of choices with costs, and you want to know if there's a path from start to finish that exactly matches your budget.

💡 This problem is about traversing a binary tree to find if any root-to-leaf path sums to a target value. Beginners often struggle because they confuse root-to-leaf paths with any path, or they don't carry the running sum correctly during recursion.

📋

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.

The number of nodes in the tree is in the range [0, 10^5]-10^9 <= Node.val <= 10^9-10^9 <= targetSum <= 10^9

💡

Example

Input"root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22"

Outputtrue

The path 5->4->11->2 sums to 22.

Input"root = [1,2,3], targetSum = 5"

Outputfalse

No root-to-leaf path sums to 5.

Input"root = [], targetSum = 0"

Outputfalse

Empty tree has no paths.

• Empty tree → false
• Single node tree where node.val == targetSum → true
• Single node tree where node.val != targetSum → false
• Tree with negative values and targetSum achievable → true

⚠️

Common Mistakes

Checking sum at non-leaf nodes

Returns true incorrectly if partial path sum equals targetSum

✅ Only check sum when node is a leaf (no children)

Not handling empty tree (null root)

Code may throw null pointer exception or return wrong result

✅ Add base case to return false if root is null

Not subtracting node value from targetSum during recursion

Sum calculation is incorrect, leading to wrong answers

✅ Pass updated targetSum - node.val in recursive calls

Using global or static variables to track sum without resetting

State leaks between recursive calls causing wrong results

✅ Pass sum as function argument or use local variables

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem deeply by exploring every root-to-leaf path without optimization. It builds intuition for carrying state during recursion.

Intuition

Traverse every root-to-leaf path, keep track of the sum along the path, and check if any path sum equals targetSum.

Algorithm

1. Start at the root with the initial sum as 0.
2. At each node, add the node's value to the running sum.
3. If the node is a leaf, check if running sum equals targetSum; if yes, return true.
4. Recursively check left and right subtrees; return true if any subtree returns true.

💡 The challenge is to correctly carry the running sum and identify leaf nodes to check sums only at leaves.

</>

Code

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == targetSum
    return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)

# Example usage:
if __name__ == '__main__':
    # Build tree [5,4,8,11,null,13,4,7,2,null,null,null,1]
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    print(hasPathSum(root, 22))  # True

Line Notes

if not root:Base case: empty subtree means no path, so return False

if not root.left and not root.right:Check if current node is a leaf node

return root.val == targetSumAt leaf, check if path sum equals targetSum

return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)Recurse on children with updated targetSum subtracting current node's value

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return root.val == targetSum;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        System.out.println(sol.hasPathSum(root, 22)); // true
    }
}

Line Notes

if (root == null) return false;Handle empty subtree base case

if (root.left == null && root.right == null)Check if current node is a leaf

return root.val == targetSum;At leaf, verify if path sum matches targetSum

return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);Recurse on left and right children with updated targetSum

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (!root->left && !root->right) return root->val == targetSum;
    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    cout << boolalpha << hasPathSum(root, 22) << endl; // true
    return 0;
}

Line Notes

if (!root) return false;Base case: empty node means no path

if (!root->left && !root->right)Check if node is leaf

return root->val == targetSum;At leaf, check if sum matches targetSum

return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);Recurse on children with updated targetSum

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function hasPathSum(root, targetSum) {
    if (!root) return false;
    if (!root.left && !root.right) return root.val === targetSum;
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

// Example usage:
const root = new TreeNode(5,
    new TreeNode(4,
        new TreeNode(11,
            new TreeNode(7),
            new TreeNode(2)
        )
    ),
    new TreeNode(8,
        new TreeNode(13),
        new TreeNode(4, null, new TreeNode(1))
    )
);
console.log(hasPathSum(root, 22)); // true

Line Notes

if (!root) return false;Empty node means no path, return false

if (!root.left && !root.right)Check if current node is leaf

return root.val === targetSum;At leaf, verify if path sum equals targetSum

return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);Recurse on left and right with updated targetSum

⏱

Complexity

TimeO(n)

SpaceO(h)

We visit each node once, so time is O(n). The recursion stack can go as deep as the tree height h, so space is O(h).

💡 For a tree with 1000 nodes and height 10, this means about 1000 operations and stack depth up to 10.

Interview Verdict: Accepted

This approach is efficient enough for most interview constraints and is the standard solution.

🧠

Iterative DFS Using Stack

💡 This approach replaces recursion with an explicit stack to avoid recursion overhead and stack overflow in very deep trees.

Intuition

Use a stack to simulate the recursive DFS, storing nodes along with the current path sum, and check sums at leaf nodes.

Algorithm

1. Initialize a stack with the root node and its value as the current sum.
2. While the stack is not empty, pop the top node and sum.
3. If the node is a leaf, check if sum equals targetSum; if yes, return true.
4. Otherwise, push the children with updated sums onto the stack.
5. If no path matches, return false.

💡 The key is to maintain the current sum alongside each node in the stack to simulate recursion state.

</>

Code

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    if not root:
        return False
    stack = [(root, root.val)]
    while stack:
        node, curr_sum = stack.pop()
        if not node.left and not node.right and curr_sum == targetSum:
            return True
        if node.right:
            stack.append((node.right, curr_sum + node.right.val))
        if node.left:
            stack.append((node.left, curr_sum + node.left.val))
    return False

# Example usage:
if __name__ == '__main__':
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    print(hasPathSum(root, 22))  # True

Line Notes

if not root:Handle empty tree edge case

stack = [(root, root.val)]Initialize stack with root and its value as current sum

node, curr_sum = stack.pop()Pop node and current path sum to process

if not node.left and not node.right and curr_sum == targetSum:Check if leaf node path sum matches targetSum

import java.util.Stack;

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, root.val));
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> current = stack.pop();
            TreeNode node = current.getKey();
            int currSum = current.getValue();
            if (node.left == null && node.right == null && currSum == targetSum) return true;
            if (node.right != null) stack.push(new Pair<>(node.right, currSum + node.right.val));
            if (node.left != null) stack.push(new Pair<>(node.left, currSum + node.left.val));
        }
        return false;
    }

    // Simple Pair class since Java 8+ doesn't have built-in Pair
    public static class Pair<K,V> {
        private K key;
        private V value;
        public Pair(K key, V value) { this.key = key; this.value = value; }
        public K getKey() { return key; }
        public V getValue() { return value; }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        System.out.println(sol.hasPathSum(root, 22)); // true
    }
}

Line Notes

if (root == null) return false;Handle empty tree

Stack<Pair<TreeNode, Integer>> stack = new Stack<>();Use stack to simulate recursion with node and current sum

Pair<TreeNode, Integer> current = stack.pop();Pop current node and sum to process

if (node.left == null && node.right == null && currSum == targetSum) return true;Check leaf node sum matches targetSum

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    stack<pair<TreeNode*, int>> stk;
    stk.push({root, root->val});
    while (!stk.empty()) {
        auto [node, currSum] = stk.top();
        stk.pop();
        if (!node->left && !node->right && currSum == targetSum) return true;
        if (node->right) stk.push({node->right, currSum + node->right->val});
        if (node->left) stk.push({node->left, currSum + node->left->val});
    }
    return false;
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    cout << boolalpha << hasPathSum(root, 22) << endl; // true
    return 0;
}

Line Notes

if (!root) return false;Empty tree means no path

stack<pair<TreeNode*, int>> stk;Stack stores nodes with current path sums

auto [node, currSum] = stk.top();Retrieve current node and sum

if (!node->left && !node->right && currSum == targetSum) return true;Check leaf node sum matches targetSum

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function hasPathSum(root, targetSum) {
    if (!root) return false;
    const stack = [[root, root.val]];
    while (stack.length > 0) {
        const [node, currSum] = stack.pop();
        if (!node.left && !node.right && currSum === targetSum) return true;
        if (node.right) stack.push([node.right, currSum + node.right.val]);
        if (node.left) stack.push([node.left, currSum + node.left.val]);
    }
    return false;
}

// Example usage:
const root = new TreeNode(5,
    new TreeNode(4,
        new TreeNode(11,
            new TreeNode(7),
            new TreeNode(2)
        )
    ),
    new TreeNode(8,
        new TreeNode(13),
        new TreeNode(4, null, new TreeNode(1))
    )
);
console.log(hasPathSum(root, 22)); // true

Line Notes

if (!root) return false;Handle empty tree case

const stack = [[root, root.val]];Initialize stack with root and its value

const [node, currSum] = stack.pop();Pop node and current sum to process

if (!node.left && !node.right && currSum === targetSum) return true;Check if leaf node path sum matches targetSum

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, so time is O(n). The stack can hold up to h nodes, where h is tree height, so space is O(h).

💡 For a tree with 1000 nodes and height 10, expect about 1000 operations and stack size up to 10.

Interview Verdict: Accepted

This iterative approach avoids recursion stack overflow and is equally efficient.

🧠

DFS with Early Stopping

💡 This approach improves efficiency by stopping recursion as soon as a valid path is found, avoiding unnecessary exploration.

Intuition

Perform DFS and return true immediately when a path with the target sum is found, pruning the search early.

Algorithm

1. Start DFS from root with current sum 0.
2. At each node, add node's value to current sum.
3. If leaf and sum equals targetSum, return true immediately.
4. Recursively check left subtree; if true, return true.
5. Otherwise, recursively check right subtree; return true if found.
6. If no path found, return false.

💡 The key is to propagate true upwards immediately to avoid exploring unnecessary paths.

</>

Code

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    print(hasPathSum(root, 22))  # True

Line Notes

def dfs(node, curr_sum):Helper function to carry current sum during DFS

if not node:Base case: null node means no path

curr_sum += node.valAdd current node's value to running sum

return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)Return true immediately if any subtree has valid path

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        return dfs(root, 0, targetSum);
    }

    private boolean dfs(TreeNode node, int currSum, int targetSum) {
        if (node == null) return false;
        currSum += node.val;
        if (node.left == null && node.right == null) return currSum == targetSum;
        return dfs(node.left, currSum, targetSum) || dfs(node.right, currSum, targetSum);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);

        System.out.println(sol.hasPathSum(root, 22)); // true
    }
}

Line Notes

return dfs(root, 0, targetSum);Start DFS with initial sum 0

if (node == null) return false;Base case for null node

currSum += node.val;Add node's value to current sum

return dfs(node.left, currSum, targetSum) || dfs(node.right, currSum, targetSum);Return true immediately if any subtree has valid path

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool dfs(TreeNode* node, int currSum, int targetSum) {
    if (!node) return false;
    currSum += node->val;
    if (!node->left && !node->right) return currSum == targetSum;
    return dfs(node->left, currSum, targetSum) || dfs(node->right, currSum, targetSum);
}

bool hasPathSum(TreeNode* root, int targetSum) {
    return dfs(root, 0, targetSum);
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    cout << boolalpha << hasPathSum(root, 22) << endl; // true
    return 0;
}

Line Notes

if (!node) return false;Base case for null node

currSum += node->val;Add current node's value to running sum

if (!node->left && !node->right) return currSum == targetSum;Check if leaf node sum matches targetSum

return dfs(node->left, currSum, targetSum) || dfs(node->right, currSum, targetSum);Return true immediately if any subtree has valid path

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function hasPathSum(root, targetSum) {
    function dfs(node, currSum) {
        if (!node) return false;
        currSum += node.val;
        if (!node.left && !node.right) return currSum === targetSum;
        return dfs(node.left, currSum) || dfs(node.right, currSum);
    }
    return dfs(root, 0);
}

// Example usage:
const root = new TreeNode(5,
    new TreeNode(4,
        new TreeNode(11,
            new TreeNode(7),
            new TreeNode(2)
        )
    ),
    new TreeNode(8,
        new TreeNode(13),
        new TreeNode(4, null, new TreeNode(1))
    )
);
console.log(hasPathSum(root, 22)); // true

Line Notes

function dfs(node, currSum) {Helper function to carry current sum

if (!node) return false;Base case for null node

currSum += node.val;Add node's value to running sum

return dfs(node.left, currSum) || dfs(node.right, currSum);Return true immediately if any subtree has valid path

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, and recursion stack depth is at most tree height h.

💡 For a tree with 1000 nodes and height 10, expect about 1000 operations and stack depth up to 10.

Interview Verdict: Accepted

Early stopping can save time in practice but asymptotic complexity remains the same.

📊

All Approaches - One-Glance Tradeoffs

💡 The recursive brute force approach is simplest and works well in most interviews. Iterative DFS is useful if recursion depth is a concern. Early stopping is a practical optimization but doesn't change complexity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(n)	O(h)	Yes (deep recursion)	N/A	Standard solution to code
2. Iterative DFS Using Stack	O(n)	O(h)	No	N/A	Mention if recursion depth is a concern
3. DFS with Early Stopping	O(n) worst case, better average	O(h)	Yes	N/A	Mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, and finally optimize. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the brute force recursive approach exploring all root-to-leaf paths.Step 3: Discuss iterative DFS to avoid recursion stack issues.Step 4: Mention early stopping optimization to prune search.Step 5: Code the chosen approach carefully and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of tree traversal, recursion, base cases, and ability to carry state during DFS. They also check if you handle edge cases and optimize when possible.

Common Follow-ups

• What if the tree is very deep? → Use iterative DFS or BFS to avoid stack overflow.
• Can you return the actual path instead of just true/false? → Modify recursion to track path nodes.

💡 These follow-ups test your ability to adapt solutions to constraints and extend functionality.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree traversal, 2) Need to check root-to-leaf paths, 3) Sum or accumulation along path matters, 4) Return boolean or path existence.

Signature Phrases

root-to-leaf pathsum equals targetleaf node

NOT This Pattern When

Problems asking for any path sum (not necessarily root-to-leaf) or maximum path sums are different patterns.

Similar Problems

Path Sum II - find all root-to-leaf paths with given sumSum Root to Leaf Numbers - sum all root-to-leaf numbers formed by node values

Practice

1. Consider the following iterative DFS code for finding all root-to-leaf paths with a given sum. Given the tree below and targetSum = 7, what is the final returned list? Tree structure: 5 / \ 4 8 / / \ 11 13 4 Target sum: 7

def pathSum(root, targetSum):
    if not root:
        return []
    res = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, current_sum = stack.pop()
        if not node.left and not node.right:
            if current_sum == targetSum:
                res.append(path)
        if node.right:
            stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
        if node.left:
            stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
    return res

easy

A. []

B. [[5, 4, 11]]

C. [[5, 4]]

D. [[5, 8, 4]]

Solution

1. Step 1: Trace paths and sums

   Paths: 5->4->11 sum=20, 5->8->13 sum=26, 5->8->4 sum=17; none equals 7.

2. Step 2: Confirm no leaf path sums to 7

   Since no leaf path sums to 7, result list remains empty.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No leaf path sums to 7, so empty list returned [OK]

Hint: Check sums only at leaf nodes [OK]

Common Mistakes:

• Confusing intermediate node sums with leaf sums
• Forgetting to check leaf condition

2. Consider this buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

3. The following code attempts to find the Lowest Common Ancestor using parent pointers. Identify the line containing the subtle bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

medium

A. Line: while p not in parent or q not in parent:

B. Line: while p:

C. Line: while q not in ancestors:

D. Line: parent = {root: None}

Solution

1. Step 1: Analyze parent map construction loop

   The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.

2. Step 2: Identify subtle bug

   If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.

3. Step 3: Explanation

   The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Loop condition must ensure both nodes are in parent map to avoid errors [OK]

Hint: Parent map construction loop must fully process both nodes [OK]

Common Mistakes:

• Assuming parent map always complete
• Ignoring incomplete parent map causing KeyError
• Misplacing bug in ancestor set loops

4. What is the space complexity of the Morris Preorder Traversal approach for summing root-to-leaf numbers in a binary tree with n nodes?

medium

A. O(1) because Morris traversal uses threaded binary tree links without extra stack

B. O(n) due to recursion stack in DFS

C. O(h) where h is tree height due to implicit stack usage

D. O(n) because all nodes are visited and stored temporarily

Solution

1. Step 1: Identify space usage in Morris traversal

   Morris traversal modifies tree pointers temporarily to avoid recursion or explicit stack, so no extra stack space is used.

2. Step 2: Confirm no auxiliary data structures

   Only constant extra variables (pointers and counters) are used, so space complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal is known for O(1) space by threading tree [OK]

Hint: Morris traversal avoids recursion and stack [OK]

Common Mistakes:

• Confusing recursion stack with Morris traversal
• Assuming O(h) due to tree height

5. Suppose you want to extend the serialization/deserialization to support binary trees where nodes can have duplicate values and the tree can be very deep (height > 10,000). Which modification is necessary to ensure correctness and efficiency?

hard

A. Use iterative BFS serialization with null markers and iterative deserialization to avoid recursion stack overflow.

B. Use recursive DFS with memoization to handle duplicates and deep trees efficiently.

C. Switch to preorder traversal without null markers to reduce string size and recursion depth.

D. Serialize only unique node values and reconstruct tree assuming balanced shape.

Solution

1. Step 1: Identify problem with deep recursion

   Recursive DFS can cause stack overflow on very deep trees.

2. Step 2: Use iterative BFS with null markers

   Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.

3. Step 3: Avoid assumptions about uniqueness or balanced shape

   Duplicates require storing all nodes explicitly; balanced assumptions break correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Iterative BFS with null markers handles deep trees and duplicates safely [OK]

Hint: Iterative BFS avoids recursion limits and preserves structure [OK]

Common Mistakes:

• Removing null markers to save space breaks reconstruction
• Using recursion on deep trees causes stack overflow
• Assuming unique values or balanced trees