Bird
Raised Fist0
Interview Preptree-dfseasyAmazonMicrosoftGoogle

Binary Tree Inorder Traversal

Choose your preparation mode4 modes available
🎯
Binary Tree Inorder Traversal
easyTREEAmazonMicrosoftGoogle

Imagine you have a family tree and want to list all members in a specific order that respects their generational hierarchy. Inorder traversal helps you visit nodes in a left-root-right sequence, which is essential in many tree-based algorithms.

💡 This problem introduces the fundamental concept of tree traversal, specifically inorder traversal. Beginners often struggle because trees are recursive structures and require understanding how to visit nodes in a specific order, which is less intuitive than linear data structures.
📋
Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder traversal visits the left subtree, then the root node, and finally the right subtree.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be positive, negative, or zero.
💡
Example
Input"root = [1,null,2,3]"
Output[1,3,2]

The tree structure is: 1 -> right child 2 -> left child 3. Inorder visits left subtree (none), root (1), then left subtree of 2 (3), then 2.

  • Single node tree → output is the single node value
  • Tree with only left children → output is nodes in descending order
  • Tree with only right children → output is nodes in ascending order
  • Empty tree (null root) → output is an empty list
⚠️
Common Mistakes
Visiting nodes in wrong order (e.g., root before left subtree)

Output does not match inorder sequence, failing correctness

✅ Ensure recursive calls and visit happen in left-root-right order

Forgetting to check for null nodes before recursion or stack operations

Runtime errors or null pointer exceptions

✅ Always check if node is null before processing

Not restoring tree structure in Morris traversal (forgetting to remove threads)

Tree structure is corrupted, causing infinite loops or incorrect output

✅ Remove temporary threads after visiting nodes

Using recursion without considering stack overflow on deep trees

Stack overflow runtime error on large or skewed trees

✅ Use iterative or Morris traversal for large inputs

Pushing nodes onto stack incorrectly in iterative approach (e.g., pushing right child first)

Traversal order is incorrect, failing the problem

✅ Push left children first and pop nodes in correct order

🧠
Brute Force (Recursive Inorder Traversal)
💡 Recursion is the most natural way to traverse trees because trees are defined recursively. This approach helps beginners understand the traversal order and recursion stack before moving to iterative methods.

Intuition

Visit the left subtree recursively, then the current node, then the right subtree recursively. This directly follows the definition of inorder traversal.

Algorithm

  1. If the current node is null, return.
  2. Recursively traverse the left subtree.
  3. Visit the current node (add its value to the result).
  4. Recursively traverse the right subtree.
💡 The challenge is to remember the exact order of operations and how recursion implicitly uses a stack to remember nodes.
</>
Code
from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)  # traverse left subtree
        result.append(node.val)  # visit node
        inorder(node.right)  # traverse right subtree
    inorder(root)
    return result

# Driver code to test
if __name__ == '__main__':
    # Construct tree: 1 -> right child 2 -> left child 3
    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(inorderTraversal(root))  # Expected output: [1,3,2]
Line Notes
def inorder(node):Defines the recursive helper function to traverse nodes
if not node:Base case to stop recursion when reaching a leaf's child
inorder(node.left)Recursively traverse the left subtree first
result.append(node.val)Visit the current node by adding its value to the result list
inorder(node.right)Recursively traverse the right subtree after visiting current node
inorder(root)Start the recursion from the root node
return resultReturn the collected inorder traversal list
import java.util.*;

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

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result); // traverse left subtree
        result.add(node.val); // visit node
        inorder(node.right, result); // traverse right subtree
    }

    // Driver code
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        Solution sol = new Solution();
        System.out.println(sol.inorderTraversal(root)); // Expected: [1, 3, 2]
    }
}
Line Notes
public List<Integer> inorderTraversal(TreeNode root)Public method to start inorder traversal and return result
if (node == null) return;Base case to stop recursion at leaf's child
inorder(node.left, result);Recursively traverse left subtree first
result.add(node.val);Visit current node by adding value to result list
inorder(node.right, result);Recursively traverse right subtree after visiting node
System.out.println(sol.inorderTraversal(root));Prints the inorder traversal result for verification
#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    void inorder(TreeNode* node, vector<int>& result) {
        if (!node) return;
        inorder(node->left, result); // traverse left subtree
        result.push_back(node->val); // visit node
        inorder(node->right, result); // traverse right subtree
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorder(root, result);
        return result;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    Solution sol;
    vector<int> res = sol.inorderTraversal(root);
    for (int v : res) cout << v << ' '; // Expected output: 1 3 2
    cout << endl;
    return 0;
}
Line Notes
void inorder(TreeNode* node, vector<int>& result)Helper function to recursively traverse nodes
if (!node) return;Base case to stop recursion at null nodes
inorder(node->left, result);Traverse left subtree first recursively
result.push_back(node->val);Visit current node by adding value to result vector
inorder(node->right, result);Traverse right subtree recursively after visiting node
vector<int> inorderTraversal(TreeNode* root)Public method to initiate traversal and return result
for (int v : res) cout << v << ' ';Prints the traversal result for verification
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function inorderTraversal(root) {
    const result = [];
    function inorder(node) {
        if (!node) return;
        inorder(node.left); // traverse left subtree
        result.push(node.val); // visit node
        inorder(node.right); // traverse right subtree
    }
    inorder(root);
    return result;
}

// Driver code
const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(inorderTraversal(root)); // Expected output: [1, 3, 2]
Line Notes
function inorder(node)Defines recursive helper function for traversal
if (!node) return;Stops recursion when node is null
inorder(node.left);Recursively traverse left subtree first
result.push(node.val);Visit current node by adding value to result array
inorder(node.right);Recursively traverse right subtree after visiting node
inorder(root);Start recursion from root node
return result;Return the collected inorder traversal array
⏱
Complexity
TimeO(n)
SpaceO(n)

Each node is visited exactly once. The recursion stack can go as deep as the height of the tree, which in worst case is O(n).

💡 For a tree with 20 nodes, this means about 20 function calls and 20 visits, which is efficient and easy to understand.
Interview Verdict: Accepted

This approach is accepted and commonly used in interviews to demonstrate understanding of recursion and tree traversal.

🧠
Iterative Inorder Traversal Using Stack
💡 Iterative traversal avoids recursion stack overflow and is often preferred in production. It helps understand how recursion can be simulated with an explicit stack.

Intuition

Use a stack to simulate the call stack of recursion: push all left children, then visit node, then move to right child.

Algorithm

  1. Initialize an empty stack and set current node to root.
  2. While current is not null or stack is not empty:
  3. Push current node and move to its left child until null.
  4. Pop from stack, visit node, then set current to right child.
  5. Repeat until all nodes are visited.
💡 The tricky part is managing the stack and current pointer correctly to maintain inorder order.
</>
Code
from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)  # push left nodes
            current = current.left
        current = stack.pop()  # visit node
        result.append(current.val)
        current = current.right  # move to right subtree
    return result

# Driver code
if __name__ == '__main__':
    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(inorderTraversal(root))  # Expected output: [1,3,2]
Line Notes
stack = []Initialize stack to simulate recursion
while current or stack:Continue until all nodes are processed
while current:Go as left as possible pushing nodes
stack.append(current)Push current node to stack before going left
current = stack.pop()Pop node to visit after left subtree done
result.append(current.val)Add node value to result list
current = current.rightMove to right subtree after visiting node
import java.util.*;

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

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current); // push left nodes
                current = current.left;
            }
            current = stack.pop(); // visit node
            result.add(current.val);
            current = current.right; // move to right subtree
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        Solution sol = new Solution();
        System.out.println(sol.inorderTraversal(root)); // Expected: [1, 3, 2]
    }
}
Line Notes
Deque<TreeNode> stack = new ArrayDeque<>();Stack to simulate recursion explicitly
while (current != null || !stack.isEmpty())Loop until all nodes are processed
while (current != null)Traverse left subtree pushing nodes
stack.push(current);Push current node before going left
current = stack.pop();Pop node to visit after left subtree
result.add(current.val);Add node value to result list
current = current.right;Move to right subtree after visiting node
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

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

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        TreeNode* current = root;
        while (current || !stk.empty()) {
            while (current) {
                stk.push(current); // push left nodes
                current = current->left;
            }
            current = stk.top();
            stk.pop(); // visit node
            result.push_back(current->val);
            current = current->right; // move to right subtree
        }
        return result;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    Solution sol;
    vector<int> res = sol.inorderTraversal(root);
    for (int v : res) cout << v << ' '; // Expected output: 1 3 2
    cout << endl;
    return 0;
}
Line Notes
stack<TreeNode*> stk;Explicit stack to simulate recursion
while (current || !stk.empty())Loop until all nodes are processed
while (current)Traverse left subtree pushing nodes
stk.push(current);Push current node before going left
current = stk.top();Get node to visit after left subtree
stk.pop();Remove node from stack after visiting
result.push_back(current->val);Add node value to result vector
current = current->right;Move to right subtree after visiting node
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;
    while (current || stack.length > 0) {
        while (current) {
            stack.push(current); // push left nodes
            current = current.left;
        }
        current = stack.pop(); // visit node
        result.push(current.val);
        current = current.right; // move to right subtree
    }
    return result;
}

// Driver code
const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(inorderTraversal(root)); // Expected output: [1, 3, 2]
Line Notes
const stack = [];Stack to simulate recursion explicitly
while (current || stack.length > 0)Loop until all nodes are processed
while (current)Traverse left subtree pushing nodes
stack.push(current);Push current node before going left
current = stack.pop();Pop node to visit after left subtree
result.push(current.val);Add node value to result array
current = current.right;Move to right subtree after visiting node
⏱
Complexity
TimeO(n)
SpaceO(n)

Each node is pushed and popped once from the stack. The stack size can be up to the height of the tree, O(n) in worst case.

💡 For 20 nodes, this means at most 20 pushes and pops, which is efficient and avoids recursion overhead.
Interview Verdict: Accepted

This approach is accepted and preferred in environments where recursion depth is a concern.

🧠
Morris Inorder Traversal (Threaded Binary Tree)
💡 Morris traversal achieves inorder traversal with O(1) extra space by temporarily modifying the tree structure. This is an advanced technique that avoids stack and recursion.

Intuition

Create temporary links (threads) from the inorder predecessor to the current node to return after left subtree traversal without a stack.

Algorithm

  1. Initialize current as root.
  2. While current is not null:
  3. If current has no left child, visit it and move to right child.
  4. Else, find the inorder predecessor of current.
  5. If predecessor's right is null, set it to current (thread) and move current to left child.
  6. If predecessor's right is current, revert the thread, visit current, and move to right child.
💡 The key is understanding how temporary threads let you traverse without extra space and how to revert changes to restore the tree.
</>
Code
from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)  # visit node
            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:
                predecessor.right = None  # remove thread
                result.append(current.val)  # visit node
                current = current.right
    return result

# Driver code
if __name__ == '__main__':
    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    print(inorderTraversal(root))  # Expected output: [1,3,2]
Line Notes
while current:Traverse nodes until all are processed
if not current.left:If no left child, visit node and move right
result.append(current.val)Visit current node by adding value to result
predecessor = current.leftFind inorder predecessor in left subtree
while predecessor.right and predecessor.right != current:Find rightmost node or existing thread
predecessor.right = currentCreate temporary thread to current node
predecessor.right = NoneRemove temporary thread to restore tree
import java.util.*;

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

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode current = root;
        while (current != null) {
            if (current.left == null) {
                result.add(current.val); // visit node
                current = current.right;
            } else {
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    predecessor.right = current; // create thread
                    current = current.left;
                } else {
                    predecessor.right = null; // remove thread
                    result.add(current.val); // visit node
                    current = current.right;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        Solution sol = new Solution();
        System.out.println(sol.inorderTraversal(root)); // Expected: [1, 3, 2]
    }
}
Line Notes
while (current != null)Traverse nodes until all processed
if (current.left == null)If no left child, visit node and move right
result.add(current.val);Visit current node by adding value to result
TreeNode predecessor = current.left;Find inorder predecessor in left subtree
while (predecessor.right != null && predecessor.right != current)Find rightmost node or existing thread
predecessor.right = current;Create temporary thread to current node
predecessor.right = null;Remove temporary thread to restore tree
#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        TreeNode* current = root;
        while (current) {
            if (!current->left) {
                result.push_back(current->val); // visit node
                current = current->right;
            } else {
                TreeNode* predecessor = current->left;
                while (predecessor->right && predecessor->right != current) {
                    predecessor = predecessor->right;
                }
                if (!predecessor->right) {
                    predecessor->right = current; // create thread
                    current = current->left;
                } else {
                    predecessor->right = nullptr; // remove thread
                    result.push_back(current->val); // visit node
                    current = current->right;
                }
            }
        }
        return result;
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    Solution sol;
    vector<int> res = sol.inorderTraversal(root);
    for (int v : res) cout << v << ' '; // Expected output: 1 3 2
    cout << endl;
    return 0;
}
Line Notes
while (current)Traverse nodes until all processed
if (!current->left)If no left child, visit node and move right
result.push_back(current->val);Visit current node by adding value to result
TreeNode* predecessor = current->left;Find inorder predecessor in left subtree
while (predecessor->right && predecessor->right != current)Find rightmost node or existing thread
predecessor->right = current;Create temporary thread to current node
predecessor->right = nullptr;Remove temporary thread to restore tree
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function inorderTraversal(root) {
    const result = [];
    let current = root;
    while (current) {
        if (!current.left) {
            result.push(current.val); // visit node
            current = current.right;
        } else {
            let predecessor = current.left;
            while (predecessor.right && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            if (!predecessor.right) {
                predecessor.right = current; // create thread
                current = current.left;
            } else {
                predecessor.right = null; // remove thread
                result.push(current.val); // visit node
                current = current.right;
            }
        }
    }
    return result;
}

// Driver code
const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(inorderTraversal(root)); // Expected output: [1, 3, 2]
Line Notes
while (current)Traverse nodes until all processed
if (!current.left)If no left child, visit node and move right
result.push(current.val);Visit current node by adding value to result
let predecessor = current.left;Find inorder predecessor in left subtree
while (predecessor.right && predecessor.right !== current)Find rightmost node or existing thread
predecessor.right = current;Create temporary thread to current node
predecessor.right = null;Remove temporary thread to restore tree
⏱
Complexity
TimeO(n)
SpaceO(1)

Each edge is visited at most twice, and no extra stack or recursion is used. Temporary threads are created and removed.

💡 For 20 nodes, this means about 40 pointer changes but no extra memory, which is optimal for space.
Interview Verdict: Accepted

This approach is accepted and shows mastery of advanced tree traversal techniques, useful in memory-constrained environments.

📊
All Approaches - One-Glance Tradeoffs
💡 For most interviews, coding the recursive or iterative approach is sufficient. Morris traversal is advanced and rarely required unless specifically asked.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Recursive)O(n)O(n) due to recursion stackYes (deep recursion)N/AGood to explain and code for clarity
2. Iterative Using StackO(n)O(n) due to explicit stackNoN/APreferred for large trees or when recursion is risky
3. Morris TraversalO(n)O(1) no extra stackNoYes (temporarily modifies tree)Mention for advanced optimization, rarely code
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force recursive approach, followed by iterative and advanced methods. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and confirm input/output format.Step 2: Describe the recursive inorder traversal as the brute force approach.Step 3: Discuss iterative traversal using a stack to avoid recursion.Step 4: Optionally mention Morris traversal for O(1) space optimization.Step 5: Code the chosen approach and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach explanation: 3min → Code: 8min → Testing & edge cases: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal order, recursion vs iteration, stack usage, and ability to optimize space. They also check for correctness on edge cases and code clarity.

Common Follow-ups

  • Can you implement preorder or postorder traversal similarly? → Yes, by changing visit order.
  • How would you handle very deep trees to avoid stack overflow? → Use iterative or Morris traversal.
💡 These follow-ups test your flexibility with traversal orders and handling recursion limits.
🔍
Pattern Recognition

When to Use

1) Problem involves binary tree traversal; 2) Need to visit nodes in left-root-right order; 3) Asked for inorder traversal specifically; 4) Output is a list of node values in inorder sequence.

Signature Phrases

inorder traversalleft subtree, root, right subtreereturn nodes in inorder sequence

NOT This Pattern When

Problems that require level order traversal or path sums are different patterns.

Similar Problems

Binary Tree Preorder Traversal - similar but visit root before childrenBinary Tree Postorder Traversal - visit root after childrenValidate Binary Search Tree - uses inorder traversal to check sorted order

Practice

(1/5)
1. Consider the following code implementing the optimal House Robber III solution. Given the tree: 3 / \ 2 3 \ \ 3 1 What is the value of rob_current when dfs is called on the root node (value 3)?
easy
A. 7
B. 6
C. 8
D. 9

Solution

  1. Step 1: Trace dfs on left child (value 2)

    dfs(2) calls dfs(null) and dfs(3). dfs(null) returns (0,0). dfs(3) returns (3,0) because it has no children. So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(0,0)=0. dfs(3) returns (3,0). For node 2: rob_current=2+0+0=2, not_rob_current=max(0,3)+max(0,0)=3. dfs(2) returns (2,3).
  2. Step 2: Trace dfs on right child (value 3)

    dfs(3) calls dfs(null) and dfs(1). dfs(1) returns (1,0). So rob_current=3+0+0=3, not_rob_current=max(0,0)+max(1,0)=1. dfs(3) returns (3,1).
  3. Step 3: Calculate rob_current at root (value 3)

    rob_current = 3 + left[1] + right[1] = 3 + 3 + 1 = 7.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Sum matches known example output 7 [OK]
Hint: Add node.val + not_rob of children for rob_current [OK]
Common Mistakes:
  • Mixing rob and not_rob values for children
  • Off-by-one in recursion returns
2. You are given a binary tree and a target sum. The task is to find all root-to-leaf paths where the sum of the node values equals the target sum. Which algorithmic approach guarantees finding all such paths efficiently?
easy
A. Greedy traversal choosing the child with the closest value to the remaining sum
B. Depth-first search (DFS) with path tracking and backtracking to explore all root-to-leaf paths
C. Dynamic programming to store sums at each node and combine results bottom-up
D. Breadth-first search (BFS) with queue to find the shortest path matching the sum

Solution

  1. Step 1: Understand problem requires all root-to-leaf paths

    Since we must find all paths, not just one, exhaustive exploration is needed.
  2. Step 2: Identify DFS with path tracking and backtracking

    DFS explores each path fully, tracking the current path and sum, backtracking to explore alternatives.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DFS explores all paths, greedy or BFS do not guarantee all paths [OK]
Hint: All root-to-leaf paths require exhaustive DFS [OK]
Common Mistakes:
  • Thinking greedy or BFS finds all paths
  • Confusing DP for path enumeration
3. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Depth-first search (DFS) with early stopping upon finding a valid path
B. Greedy traversal choosing the child with the closest value to the target sum
C. Dynamic programming with memoization of partial sums at each node
D. Breadth-first search (BFS) exploring all paths level by level

Solution

  1. Step 1: Understand the problem constraints

    The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.
  2. Step 2: Identify the best approach

    DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DFS explores paths fully and stops early when possible [OK]
Hint: Early stopping DFS avoids unnecessary traversal [OK]
Common Mistakes:
  • Believing greedy approach works for sums
  • Confusing BFS with DFS for path sums
4. Consider the following buggy code for checking if a binary tree is symmetric. Which line contains the subtle bug that causes incorrect results for asymmetric trees?
def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return True
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True
medium
A. Line 5: if t1.val != t2.val: return False
B. Line 3: if not t1 or not t2: return True
C. Line 6: return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
D. Line 8: return isMirror(root.left, root.right) if root else True

Solution

  1. Step 1: Analyze base case for null nodes

    The line returns true if either t1 or t2 is null, but it should only return true if both are null.
  2. Step 2: Identify that returning true when only one node is null causes false positives

    This causes asymmetric trees with missing nodes on one side to be incorrectly considered symmetric.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Base case must check both nodes null equality, not just one [OK]
Hint: Base case must return true only if both nodes are null [OK]
Common Mistakes:
  • Returning true if only one node is null
  • Forgetting to check node values before recursion
  • Mixing left and right subtree comparisons
5. Suppose you want to invert a binary tree where nodes can have an arbitrary number of children (not just two). Which modification to the inversion algorithm correctly generalizes the inversion to this n-ary tree?
hard
A. Swap only the first and last child pointers recursively, leaving others unchanged.
B. Use BFS to swap children pairwise at each level without recursion.
C. Recursively invert each child's subtree, then reverse the list of children in-place.
D. Invert only the leftmost and rightmost subtrees recursively, ignoring middle children.

Solution

  1. Step 1: Understand inversion for binary tree swaps left and right children

    For n-ary trees, inversion means reversing the order of children after inverting each child's subtree.
  2. Step 2: Generalize recursion and reversal

    Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.
  3. Step 3: Evaluate other options

    Swapping only first and last or partial BFS swaps do not fully invert the tree structure.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Recursion plus reversing children list generalizes inversion correctly [OK]
Hint: Invert subtrees recursively, then reverse children list for n-ary trees [OK]
Common Mistakes:
  • Swapping only some children pairs
  • Ignoring recursion on all children
  • Using BFS without recursion for full inversion
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