Binary Tree Inorder Traversal

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive)	O(n)	O(n) due to recursion stack	Yes (deep recursion)	N/A	Good to explain and code for clarity
2. Iterative Using Stack	O(n)	O(n) due to explicit stack	No	N/A	Preferred for large trees or when recursion is risky
3. Morris Traversal	O(n)	O(1) no extra stack	No	Yes (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. Consider the following iterative postorder traversal code to compute the maximum path sum in a binary tree. Given the tree below, what is the final value of max_sum after the function completes? Tree structure: ``` 1 / 2 3 ```

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

def maxPathSum(root):
    if not root:
        return 0
    max_sum = float('-inf')
    stack = []
    node = root
    last_visited = null
    gain_map = {}

    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right and last_visited != peek.right:
                node = peek.right
            else:
                left_gain = max(gain_map.get(peek.left, 0), 0)
                right_gain = max(gain_map.get(peek.right, 0), 0)
                current_path_sum = peek.val + left_gain + right_gain
                max_sum = max(max_sum, current_path_sum)
                gain_map[peek] = peek.val + max(left_gain, right_gain)
                last_visited = stack.pop()
    return max_sum

easy

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Trace left subtree gain

   Node 2 has no children, so left_gain=0, right_gain=0, current_path_sum=2, max_sum updated to 2, gain_map[2]=2.

2. Step 2: Trace root and right subtree

   Node 3 has no children, current_path_sum=3, max_sum updated to 3, gain_map[3]=3. For root 1, left_gain=2, right_gain=3, current_path_sum=1+2+3=6, max_sum updated to 6.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of path 2 -> 1 -> 3 is 6 [OK]

Hint: Sum path 2->1->3 yields max sum 6 [OK]

Common Mistakes:

• Ignoring one child's gain leads to 5 or 4
• Off-by-one in gain_map updates
• Returning partial sums instead of max path sum

2. Consider the following code snippet implementing the optimal countNodes function for a complete binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final return value of countNodes(root)?

easy

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Calculate tree height

   Height h = 3 (nodes 1 -> 2 -> 4).

2. Step 2: Binary search on last level nodes

   Last level has indices 0 to 3. Check existence: - idx=0 exists (node 4) - idx=1 does not exist So left ends at 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count = (2^(3-1)-1) + left = 3 + 1 = 4 [OK]

Hint: Count = perfect nodes + last level nodes found [OK]

Common Mistakes:

• Off-by-one in binary search bounds
• Miscounting last level nodes

3. 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

4. What is the time complexity of the BFS-based algorithm to compute the maximum depth of a binary tree with n nodes, and why might the following common misconception be incorrect? Options:

medium

A. O(n), but with O(n) auxiliary space for the queue at the widest level

B. O(n), because each node is visited exactly once in BFS

C. O(n log n), because each level requires sorting nodes

D. O(n^2), because each node is enqueued and dequeued multiple times

Solution

1. Step 1: Identify time complexity

   BFS visits each node exactly once, so time complexity is O(n).

2. Step 2: Identify space complexity and common misconception

   Queue can hold up to O(n) nodes at the widest level, so auxiliary space is O(n). The misconception is thinking nodes are processed multiple times, leading to O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node enqueued and dequeued once; max queue size O(n) [OK]

Hint: BFS visits each node once; space depends on max level width [OK]

Common Mistakes:

• Assuming multiple visits per node
• Confusing sorting with traversal
• Ignoring queue space usage

5. Suppose the binary tree nodes can have duplicate values, and you are given preorder and inorder traversals with duplicates. Which modification to the standard iterative approach is necessary to correctly reconstruct the tree?

hard

A. Use a hash map from value to a list of all indices in inorder, and track which index to use next during construction.

B. Ignore duplicates and build the tree as usual, since preorder and inorder uniquely identify the tree.

C. Sort the preorder array to remove duplicates before building the tree.

D. Use a brute force approach with array slicing to handle duplicates correctly.

Solution

1. Step 1: Understand the problem with duplicates

   Duplicates cause ambiguity in mapping values to inorder indices, breaking the unique root index lookup.

2. Step 2: Modify data structure

   Store all indices of each value in a list, and track which occurrence to use next to maintain correct subtree boundaries.

3. Step 3: Avoid naive approaches

   Ignoring duplicates or sorting breaks traversal properties; brute force is inefficient and unnecessary with proper tracking.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value resolves duplicate ambiguity [OK]

Hint: Track all inorder indices per value to handle duplicates [OK]

Common Mistakes:

• Assuming unique values always
• Sorting preorder breaks tree structure
• Using brute force causes inefficiency