Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoftFacebook

Path Sum

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Pure Recursion)O(n)O(h)Yes (deep recursion)N/AStandard solution to code
2. Iterative DFS Using StackO(n)O(h)NoN/AMention if recursion depth is a concern
3. DFS with Early StoppingO(n) worst case, better averageO(h)YesN/AMention 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/5)
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. You need to convert a binary tree into a string and then reconstruct the exact same tree from that string. Which approach guarantees that the tree structure, including null children, is preserved and can be reconstructed efficiently?
easy
A. Use level order traversal (BFS) including null markers for missing children, then deserialize by reading nodes level by level.
B. Use a greedy traversal that records only node values without null markers, then reconstruct by inserting nodes in order.
C. Use dynamic programming to store subtree encodings and reconstruct from stored subtrees.
D. Use inorder traversal without null markers and reconstruct by assuming a balanced tree.

Solution

  1. Step 1: Understand the need for null markers

    Without null markers, the tree structure cannot be uniquely reconstructed because missing children are ambiguous.
  2. Step 2: Recognize BFS with null markers preserves structure

    Level order traversal with null markers records nodes level by level, capturing the exact shape of the tree, enabling correct deserialization.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Level order with null markers uniquely encodes tree structure [OK]
Hint: Null markers are essential to preserve tree shape [OK]
Common Mistakes:
  • Ignoring null markers leads to ambiguous deserialization
  • Assuming inorder traversal alone can reconstruct arbitrary trees
  • Using greedy or DP approaches that don't preserve structure
3. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result
medium
A. Missing line resetting predecessor.right = None to remove thread
B. Line moving current to current.left after creating thread
C. Line appending current.val after detecting thread
D. Line setting predecessor.right = current (creating thread)

Solution

  1. Step 1: Identify thread removal step

    Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.
  2. Step 2: Locate missing removal

    The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without removing thread, traversal loops endlessly [OK]
Hint: Always remove threads to restore tree [OK]
Common Mistakes:
  • Forgetting to remove thread
  • Appending node before removing thread
  • Incorrectly creating thread
4. What is the time complexity of the Morris preorder traversal algorithm on a binary tree with n nodes, and why might some candidates mistakenly think it is higher?
medium
A. O(n log n) because each node is visited multiple times during threading
B. O(n) but with O(n) auxiliary space due to recursion stack
C. O(n^2) because the inner loop to find predecessor can traverse many nodes repeatedly
D. O(n) because each edge is traversed at most twice during threading and restoration

Solution

  1. Step 1: Identify traversal of nodes and edges

    Each node is visited once, and each edge is traversed at most twice (once to create thread, once to remove it).
  2. Step 2: Explain why complexity is linear

    Because total edge traversals sum to O(n), the overall time complexity is O(n).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Threading and restoring links cause at most two visits per edge [OK]
Hint: Each edge visited max twice -> O(n) time [OK]
Common Mistakes:
  • Assuming inner loop causes O(n^2)
  • Confusing threading with recursion stack space
  • Thinking threading causes log n overhead
5. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?
medium
A. O(n) due to storing all nodes in a list during traversal
B. O(1) because the algorithm modifies the tree in-place without extra memory
C. O(log n) because the tree height is always balanced and recursion stack is limited
D. O(h) due to recursion stack depth in worst case of skewed tree

Solution

  1. Step 1: Identify auxiliary space usage

    The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.
  2. Step 2: Clarify why O(h) not O(1) or O(n)

    It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Recursion stack space equals tree height h [OK]
Hint: Recursion stack space equals tree height h [OK]
Common Mistakes:
  • Assuming O(1) space because of in-place modification
  • Confusing recursion stack with explicit data structures
  • Assuming balanced tree always so O(log n) space
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard