Bird
Raised Fist0
Interview Preptree-dfseasyGoogleAmazonFacebook

Invert Binary Tree

Choose your preparation mode4 modes available
🎯
Invert Binary Tree
easyTREEGoogleAmazonFacebook

Imagine you have a family tree diagram and want to see it flipped horizontally, like looking at it in a mirror. This problem asks you to invert a binary tree in a similar way.

💡 This problem is about transforming a binary tree by swapping its left and right children at every node. Beginners often struggle because they may not realize that a simple recursive traversal with swapping can solve it efficiently, and might try complicated or iterative methods first.
📋
Problem Statement

Given the root of a binary tree, invert the tree, and return its root. Inverting a binary tree means swapping the left and right children of all nodes in the tree.

The number of nodes in the tree is in the range [1, 10^5].Node values can be any integer.The tree can be unbalanced.
💡
Example
Input"root = [4,2,7,1,3,6,9]"
Output[4,7,2,9,6,3,1]

The original tree has root 4 with left child 2 and right child 7. After inversion, 2 and 7 are swapped, and this swapping continues recursively for all nodes.

  • Single node tree → output is the same single node
  • Tree with only left children → output is a tree with only right children
  • Tree with only right children → output is a tree with only left children
  • Empty tree (null root) → output is null
⚠️
Common Mistakes
Not swapping children after recursive calls

Tree remains unchanged or partially inverted

✅ Ensure swapping left and right children after recursive inversion of subtrees

Swapping children before recursive calls

Leads to incorrect inversion because subtrees are not inverted properly

✅ Perform recursive inversion first, then swap children

Not handling null root (empty tree)

Code may throw null pointer exceptions or runtime errors

✅ Add base case to return null if root is null

Using iterative approach without checking for null children before enqueueing

Queue may contain nulls causing errors during processing

✅ Check if child nodes are not null before adding to queue

Confusing left and right pointers during swap

Tree structure becomes corrupted or inversion is incorrect

✅ Use a temporary variable or tuple unpacking to swap correctly

🧠
Brute Force (Pure Recursion)
💡 Starting with a simple recursive approach helps understand the problem deeply by directly applying the definition of inversion without worrying about optimization.

Intuition

At each node, recursively invert the left and right subtrees, then swap them. This directly follows the problem statement.

Algorithm

  1. If the current node is null, return null.
  2. Recursively invert the left subtree.
  3. Recursively invert the right subtree.
  4. Swap the left and right children of the current node.
  5. Return the current node.
💡 The recursion naturally traverses the tree postorder, ensuring children are inverted before swapping, which is key to correct inversion.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(root):
    if root is None:
        return None
    left_inverted = invertTree(root.left)
    right_inverted = invertTree(root.right)
    root.left, root.right = right_inverted, left_inverted
    return root

# Example usage:
# root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
# inverted_root = invertTree(root)
Line Notes
def invertTree(root):Defines the main function to invert the binary tree starting at root
if root is None:Base case: if node is null, nothing to invert, return None
left_inverted = invertTree(root.left)Recursively invert the left subtree first
right_inverted = invertTree(root.right)Recursively invert the right subtree next
root.left, root.right = right_inverted, left_invertedSwap the inverted left and right subtrees to invert current node
return rootReturn the current node after inversion to link back to parent
public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode leftInverted = invertTree(root.left);
        TreeNode rightInverted = invertTree(root.right);
        root.left = rightInverted;
        root.right = leftInverted;
        return root;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(4);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(7);
    //     root.left.left = new TreeNode(1);
    //     root.left.right = new TreeNode(3);
    //     root.right.left = new TreeNode(6);
    //     root.right.right = new TreeNode(9);
    //     Solution sol = new Solution();
    //     TreeNode inverted = sol.invertTree(root);
    // }
}
Line Notes
public TreeNode invertTree(TreeNode root) {Main method to invert the tree starting at root
if (root == null) return null;Base case: if node is null, return null immediately
TreeNode leftInverted = invertTree(root.left);Recursively invert left subtree
TreeNode rightInverted = invertTree(root.right);Recursively invert right subtree
root.left = rightInverted;Assign inverted right subtree to left child
root.right = leftInverted;Assign inverted left subtree to right child
return root;Return current node after inversion
#include <iostream>
using namespace std;

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

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    TreeNode* leftInverted = invertTree(root->left);
    TreeNode* rightInverted = invertTree(root->right);
    root->left = rightInverted;
    root->right = leftInverted;
    return root;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(4);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(7);
//     root->left->left = new TreeNode(1);
//     root->left->right = new TreeNode(3);
//     root->right->left = new TreeNode(6);
//     root->right->right = new TreeNode(9);
//     TreeNode* inverted = invertTree(root);
//     return 0;
// }
Line Notes
TreeNode* invertTree(TreeNode* root) {Function to invert the binary tree starting at root pointer
if (root == nullptr) return nullptr;Base case: if node pointer is null, return null
TreeNode* leftInverted = invertTree(root->left);Recursively invert left subtree
TreeNode* rightInverted = invertTree(root->right);Recursively invert right subtree
root->left = rightInverted;Assign inverted right subtree to left child pointer
root->right = leftInverted;Assign inverted left subtree to right child pointer
return root;Return current node pointer after inversion
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function invertTree(root) {
    if (root === null) return null;
    const leftInverted = invertTree(root.left);
    const rightInverted = invertTree(root.right);
    root.left = rightInverted;
    root.right = leftInverted;
    return root;
}

// Example usage:
// const root = new TreeNode(4,
//     new TreeNode(2, new TreeNode(1), new TreeNode(3)),
//     new TreeNode(7, new TreeNode(6), new TreeNode(9))
// );
// const inverted = invertTree(root);
// console.log(inverted);
Line Notes
function invertTree(root) {Defines the function to invert the binary tree starting at root
if (root === null) return null;Base case: if node is null, return null immediately
const leftInverted = invertTree(root.left);Recursively invert left subtree
const rightInverted = invertTree(root.right);Recursively invert right subtree
root.left = rightInverted;Assign inverted right subtree to left child
root.right = leftInverted;Assign inverted left subtree to right child
return root;Return current node after inversion
⏱
Complexity
TimeO(n)
SpaceO(h)

Each node is visited 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 of 10, which is efficient.
Interview Verdict: Accepted

This approach is efficient and accepted for all valid inputs, making it a solid baseline solution.

🧠
Iterative Approach Using Queue (BFS)
💡 This approach uses a queue to invert the tree level by level, which helps understand iterative tree traversal and avoids recursion stack issues.

Intuition

Use a queue to traverse the tree in breadth-first order, swapping children at each node as you go.

Algorithm

  1. If the root is null, return null.
  2. Initialize a queue and enqueue the root node.
  3. While the queue is not empty:
  4. Dequeue a node from the queue.
  5. Swap its left and right children.
  6. If left child is not null, enqueue it.
  7. If right child is not null, enqueue it.
  8. Return the root node.
💡 This approach uses level order traversal to visit nodes systematically and invert them without recursion.
</>
Code
from collections import deque

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

def invertTree(root):
    if root is None:
        return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return root

# Example usage:
# root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
# inverted_root = invertTree(root)
Line Notes
from collections import dequeImport deque for efficient queue operations
if root is None:Handle empty tree edge case
queue = deque([root])Initialize queue with root node to start BFS
while queue:Process nodes until queue is empty
node = queue.popleft()Dequeue current node to process
node.left, node.right = node.right, node.leftSwap left and right children of current node
if node.left:If left child exists after swap, enqueue it for later processing
if node.right:If right child exists after swap, enqueue it for later processing
return rootReturn the root of the inverted tree
import java.util.LinkedList;
import java.util.Queue;

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

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        return root;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(4);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(7);
    //     root.left.left = new TreeNode(1);
    //     root.left.right = new TreeNode(3);
    //     root.right.left = new TreeNode(6);
    //     root.right.right = new TreeNode(9);
    //     Solution sol = new Solution();
    //     TreeNode inverted = sol.invertTree(root);
    // }
}
Line Notes
if (root == null) return null;Handle empty tree case immediately
Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS traversal
queue.add(root);Add root node to start BFS
while (!queue.isEmpty()) {Process nodes until queue is empty
TreeNode node = queue.poll();Dequeue current node
TreeNode temp = node.left;Temporarily store left child for swapping
node.left = node.right;Assign right child to left
node.right = temp;Assign stored left child to right
if (node.left != null) queue.add(node.left);Enqueue left child if exists
if (node.right != null) queue.add(node.right);Enqueue right child if exists
return root;Return root of inverted tree
#include <iostream>
#include <queue>
using namespace std;

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

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        TreeNode* temp = node->left;
        node->left = node->right;
        node->right = temp;
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return root;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(4);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(7);
//     root->left->left = new TreeNode(1);
//     root->left->right = new TreeNode(3);
//     root->right->left = new TreeNode(6);
//     root->right->right = new TreeNode(9);
//     TreeNode* inverted = invertTree(root);
//     return 0;
// }
Line Notes
if (root == nullptr) return nullptr;Handle empty tree case
queue<TreeNode*> q;Initialize queue for BFS
q.push(root);Start BFS with root node
while (!q.empty()) {Process nodes until queue is empty
TreeNode* node = q.front();Get current node from queue front
q.pop();Remove current node from queue
TreeNode* temp = node->left;Store left child temporarily for swapping
node->left = node->right;Assign right child to left
node->right = temp;Assign stored left child to right
if (node->left) q.push(node->left);Enqueue left child if exists
if (node->right) q.push(node->right);Enqueue right child if exists
return root;Return root of inverted tree
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function invertTree(root) {
    if (root === null) return null;
    const queue = [root];
    while (queue.length > 0) {
        const node = queue.shift();
        [node.left, node.right] = [node.right, node.left];
        if (node.left !== null) queue.push(node.left);
        if (node.right !== null) queue.push(node.right);
    }
    return root;
}

// Example usage:
// const root = new TreeNode(4,
//     new TreeNode(2, new TreeNode(1), new TreeNode(3)),
//     new TreeNode(7, new TreeNode(6), new TreeNode(9))
// );
// const inverted = invertTree(root);
// console.log(inverted);
Line Notes
if (root === null) return null;Handle empty tree edge case
const queue = [root];Initialize queue with root node for BFS
while (queue.length > 0) {Process nodes until queue is empty
const node = queue.shift();Dequeue node from front of queue
[node.left, node.right] = [node.right, node.left];Swap left and right children using destructuring
if (node.left !== null) queue.push(node.left);Enqueue left child if exists
if (node.right !== null) queue.push(node.right);Enqueue right child if exists
return root;Return root of inverted tree
⏱
Complexity
TimeO(n)
SpaceO(n)

Each node is visited once, so time is O(n). The queue can hold up to O(n) nodes in the worst case (e.g., a full level).

💡 For a tree with 1000 nodes, this means about 1000 operations and queue size up to 1000 in worst case, which is manageable.
Interview Verdict: Accepted

This iterative approach is also accepted and useful when recursion depth is a concern.

🧠
Optimized Recursive Approach (In-place Postorder Traversal)
💡 This approach is a refined recursive method that emphasizes in-place swapping during postorder traversal, minimizing extra variables and improving clarity.

Intuition

Invert left and right subtrees recursively, then swap them directly on the current node without extra variables.

Algorithm

  1. If the current node is null, return null.
  2. Recursively invert the left subtree.
  3. Recursively invert the right subtree.
  4. Swap the left and right children of the current node in-place.
  5. Return the current node.
💡 This approach uses postorder traversal to ensure children are inverted before swapping, which is essential for correctness.
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(root):
    if root is None:
        return None
    invertTree(root.left)
    invertTree(root.right)
    root.left, root.right = root.right, root.left
    return root

# Example usage:
# root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
# inverted_root = invertTree(root)
Line Notes
def invertTree(root):Defines the function to invert the tree starting at root
if root is None:Base case: return None if node is null
invertTree(root.left)Recursively invert left subtree first
invertTree(root.right)Recursively invert right subtree next
root.left, root.right = root.right, root.leftSwap left and right children in-place after inversion
return rootReturn current node after inversion
public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     TreeNode root = new TreeNode(4);
    //     root.left = new TreeNode(2);
    //     root.right = new TreeNode(7);
    //     root.left.left = new TreeNode(1);
    //     root.left.right = new TreeNode(3);
    //     root.right.left = new TreeNode(6);
    //     root.right.right = new TreeNode(9);
    //     Solution sol = new Solution();
    //     TreeNode inverted = sol.invertTree(root);
    // }
}
Line Notes
public TreeNode invertTree(TreeNode root) {Main method to invert tree starting at root
if (root == null) return null;Base case: return null if node is null
invertTree(root.left);Recursively invert left subtree
invertTree(root.right);Recursively invert right subtree
TreeNode temp = root.left;Temporarily store left child for swapping
root.left = root.right;Assign right child to left
root.right = temp;Assign stored left child to right
return root;Return current node after inversion
#include <iostream>
using namespace std;

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

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    invertTree(root->left);
    invertTree(root->right);
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    return root;
}

// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(4);
//     root->left = new TreeNode(2);
//     root->right = new TreeNode(7);
//     root->left->left = new TreeNode(1);
//     root->left->right = new TreeNode(3);
//     root->right->left = new TreeNode(6);
//     root->right->right = new TreeNode(9);
//     TreeNode* inverted = invertTree(root);
//     return 0;
// }
Line Notes
TreeNode* invertTree(TreeNode* root) {Function to invert tree starting at root pointer
if (root == nullptr) return nullptr;Base case: return null if node pointer is null
invertTree(root->left);Recursively invert left subtree
invertTree(root->right);Recursively invert right subtree
TreeNode* temp = root->left;Temporarily store left child pointer for swapping
root->left = root->right;Assign right child pointer to left
root->right = temp;Assign stored left child pointer to right
return root;Return current node pointer after inversion
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function invertTree(root) {
    if (root === null) return null;
    invertTree(root.left);
    invertTree(root.right);
    [root.left, root.right] = [root.right, root.left];
    return root;
}

// Example usage:
// const root = new TreeNode(4,
//     new TreeNode(2, new TreeNode(1), new TreeNode(3)),
//     new TreeNode(7, new TreeNode(6), new TreeNode(9))
// );
// const inverted = invertTree(root);
// console.log(inverted);
Line Notes
function invertTree(root) {Defines function to invert tree starting at root
if (root === null) return null;Base case: return null if node is null
invertTree(root.left);Recursively invert left subtree
invertTree(root.right);Recursively invert right subtree
[root.left, root.right] = [root.right, root.left];Swap left and right children in-place using destructuring
return root;Return current node after inversion
⏱
Complexity
TimeO(n)
SpaceO(h)

Each node is visited once, so time is O(n). The recursion stack depth is O(h), where h is tree height.

💡 For a balanced tree with 1000 nodes, this means about 1000 operations and stack depth about 10, which is efficient.
Interview Verdict: Accepted

This is the cleanest recursive approach and is accepted in interviews and production code.

📊
All Approaches - One-Glance Tradeoffs
💡 In most interviews, the recursive approach (Approach 3) is preferred for its clarity and simplicity. Iterative approach is useful if recursion depth is a concern.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute Force (Pure Recursion)O(n)O(h)Yes (deep recursion)N/AMention and code as baseline solution
2. Iterative Approach Using Queue (BFS)O(n)O(n)NoN/AMention as alternative to recursion
3. Optimized Recursive Approach (In-place Postorder Traversal)O(n)O(h)Yes (deep recursion)N/APreferred approach to code in interviews
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force recursive approach, followed by iterative and optimized recursive methods. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive approach and its intuition.Step 3: Code the recursive solution and test with examples.Step 4: Discuss iterative BFS approach to avoid recursion stack issues.Step 5: Present the optimized recursive approach for clarity and in-place inversion.Step 6: Analyze time and space complexity for each approach.Step 7: Discuss edge cases and how your code handles them.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 5min. Total ~18min

What the Interviewer Tests

The interviewer tests your understanding of tree traversal, recursion, and ability to transform trees in-place. They also check if you handle edge cases and can optimize your solution.

Common Follow-ups

  • Can you invert the tree iteratively? → Use BFS with a queue to swap nodes level by level.
  • What is the space complexity of your recursive solution? → O(h) due to recursion stack, where h is tree height.
💡 These follow-ups test your flexibility with iterative solutions and understanding of recursion space costs.
🔍
Pattern Recognition

When to Use

1) Problem involves binary tree transformation, 2) Requires swapping or rearranging children, 3) Recursive or DFS traversal is natural, 4) Output is a modified tree structure.

Signature Phrases

invert the treeswap left and right childrenmirror image of the tree

NOT This Pattern When

Problems that only require traversal without modification, or those that require path sums or subtree counts.

Similar Problems

Symmetric Tree - checks if a tree is a mirror of itselfMaximum Depth of Binary Tree - uses DFS traversalBinary Tree Upside Down - another tree transformation problem

Practice

(1/5)
1. Given the following Morris inorder traversal code, what is the final output list after running inorderTraversal on this tree?

Tree structure:
2
/ \ 1 3
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
easy
A. [1, 2, 3]
B. [1, 3, 2]
C. [2, 1, 3]
D. [3, 2, 1]

Solution

  1. Step 1: Trace traversal starting at root=2

    Current=2 has left child 1, find predecessor in left subtree: node 1 (no right child). Create thread from 1.right to 2, move current to 1.
  2. Step 2: Visit node 1 (no left child), append 1, move current to 1.right which points to 2 (thread).

    Remove thread, append 2, move current to 2.right=3. Node 3 has no left child, append 3, move current to null.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inorder traversal of tree 1,2,3 is [1,2,3] [OK]
Hint: Inorder traversal visits left, root, right [OK]
Common Mistakes:
  • Appending before removing thread
  • Visiting root before left subtree
  • Confusing preorder with inorder output
2. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

    1
   / \
  2   3
def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result
easy
A. [2, 1, 3]
B. [1, 2, 3]
C. [1, 3, 2]
D. [3, 1, 2]

Solution

  1. Step 1: Trace first iteration with current=1

    Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.
  2. Step 2: Trace second iteration with current=2

    Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).
  3. Step 3: Detect thread at 2.right=1

    Since predecessor.right == current, reset 2.right=None, move current=1.right=3.
  4. Step 4: Trace current=3

    Node 3 has no left child, append 3, move current=3.right=None, loop ends.
  5. Final Answer:

    Option B -> Option B
  6. Quick Check:

    Output matches preorder traversal [1,2,3] [OK]
Hint: Morris preorder appends root before left subtree [OK]
Common Mistakes:
  • Appending nodes in wrong order
  • Not resetting threaded links
  • Confusing left and right child traversal
3. You are given two arrays representing the preorder and inorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant subtree searches?
easy
A. Use breadth-first search to build the tree level by level from preorder and inorder arrays.
B. Use a greedy approach that picks nodes based on preorder and attaches them arbitrarily to the left or right.
C. Use dynamic programming to store subtree results and combine them for the full tree.
D. Use recursion with a hash map to quickly find root indices in inorder traversal, avoiding repeated searches.

Solution

  1. Step 1: Understand the problem constraints

    Reconstructing a binary tree from preorder and inorder requires knowing root positions quickly to split subtrees.
  2. Step 2: Identify the optimal approach

    Using a hash map for inorder indices allows O(1) root lookups, avoiding repeated O(n) searches in recursion.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Hash map lookup avoids repeated scanning [OK]
Hint: Hash map lookup avoids repeated inorder searches [OK]
Common Mistakes:
  • Assuming greedy or BFS can reconstruct tree correctly
  • Confusing DP with tree construction
  • Ignoring the need for quick root index lookup
4. Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:
def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                # Bug here
                current = current.right
    return result
medium
A. Line resetting predecessor.right to None is missing in the else block
B. Appending current.val before moving to left child is incorrect
C. The inner while loop condition should check predecessor.left instead of predecessor.right
D. The check for current.left being None should be after the else block

Solution

  1. Step 1: Identify missing restoration of tree structure

    In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.
  2. Step 2: Locate missing line

    The else block lacks the line predecessor.right = None, causing the threaded link to persist.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without resetting, tree remains modified after traversal [OK]
Hint: Always reset threaded links to None after use [OK]
Common Mistakes:
  • Forgetting to restore tree structure
  • Appending nodes in wrong order
  • Incorrect loop conditions
5. Consider the following buggy deserialization code snippet for BFS-based tree reconstruction. Which line contains the subtle bug that causes incorrect tree structure when deserializing?
def deserialize(data):
    if not data:
        return None
    vals = data.split(',')
    root = TreeNode(int(vals[0]))
    queue = deque([root])
    i = 1
    while queue:
        node = queue.popleft()
        if vals[i] != 'X':
            node.left = TreeNode(int(vals[i]))
            queue.append(node.left)
        i += 1
        if vals[i] != 'X':
            node.right = TreeNode(int(vals[i]))
            queue.append(node.right)
        i += 1
    return root
medium
A. Line: if vals[i] != 'X': (left child check)
B. Line: i += 1 (after left child assignment)
C. Line: if vals[i] != 'X': (right child check)
D. Line: while queue: (loop condition)

Solution

  1. Step 1: Identify potential infinite loop

    The loop condition 'while queue:' does not check if 'i' has exceeded vals length, risking index out of range or infinite loop.
  2. Step 2: Understand impact on deserialization

    Without checking 'i < len(vals)', the loop may continue after all nodes processed, causing errors or incorrect tree structure.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Loop condition must ensure 'i' stays within bounds to avoid deserialization bugs [OK]
Hint: Loop must check index bounds to avoid infinite loops [OK]
Common Mistakes:
  • Not checking index bounds in deserialization loops
  • Mixing up left and right child assignments
  • Forgetting to append children to queue
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