Bird
Raised Fist0
Interview Preptree-dfseasyGoogleAmazonFacebook

Invert Binary Tree

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize / Setup

The algorithm starts at the root node with value 4. The call stack is initialized with the root node marked as entered, ready to process its subtrees.

💡 Setting up the initial call stack and marking the root as active shows where recursion begins.
Line:def invertTree(root): if root is null: return null
💡 The root node is the starting point for the recursive inversion.
📊
Invert Binary Tree - Watch the Algorithm Execute, Step by Step
Watching the algorithm step through each node and swap children visually reveals the recursive nature and in-place transformation, making the inversion concept intuitive.
Step 1/15
·Active fill★Answer cell
Current node: 1
4271369
DFS Stack
1 (entered)
Current node: 2
4271369
DFS Stack
2 (entered)1 (entered)
Current node: 4
4271369
DFS Stack
4 (entered)2 (entered)1 (entered)
4271369
DFS Stack
4 (entered)2 (entered)1 (entered)
4271369
DFS Stack
4 (entered)2 (entered)1 (entered)
Current node: 4
4271369
DFS Stack
2 (entered)1 (entered)
Return: 4
Current node: 5
4271369
DFS Stack
5 (entered)2 (entered)1 (entered)
Current node: 6
4271369
DFS Stack
6 (entered)3 (entered)2 (entered)1 (entered)
Current node: 6
4271369
DFS Stack
3 (entered)2 (entered)1 (entered)
Return: 6
Current node: 7
4271369
DFS Stack
3 (entered)2 (entered)1 (entered)
Return: 7
Current node: 3
4271369
DFS Stack
2 (entered)1 (entered)
Return: 3
Current node: 2
4271369
DFS Stack
1 (entered)
Return: 2
Current node: 3
4271369
DFS Stack
3 (entered)1 (entered)
Current node: 1
4271369
DFS Stack
1 (returning)
Return: 1
4271369
Return: 1

Key Takeaways

✓ The inversion is performed in-place using postorder traversal, ensuring children are inverted before swapping at the parent.

This insight is hard to see from code alone because the recursion order and in-place swaps are implicit.

✓ Leaf nodes serve as base cases where recursion returns immediately, anchoring the inversion process.

Visualizing leaf nodes returning clarifies how recursion bottoms out and starts unwinding.

✓ Swapping left and right children at each node progressively transforms the tree structure from bottom up.

Seeing the subtree swaps step-by-step reveals how local changes combine to invert the entire tree.

Practice

(1/5)
1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?
easy
A. Use a breadth-first search (BFS) to visit nodes level by level.
B. Use a recursive preorder traversal that visits root, left, then right nodes.
C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.
D. Use a dynamic programming approach to store and reuse subtree results.

Solution

  1. Step 1: Understand traversal order requirement

    Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
  2. Step 2: Identify approach with O(1) space

    Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Morris traversal is known for O(1) space inorder traversal [OK]
Hint: Morris traversal enables inorder with O(1) space [OK]
Common Mistakes:
  • Confusing preorder with inorder traversal order
  • Assuming BFS can produce inorder sequence
  • Thinking DP applies to traversal order
2. You are given a binary tree that is complete (all levels except possibly the last are fully filled, and nodes in the last level are as far left as possible). You need to count the total number of nodes efficiently. Which approach guarantees the optimal time complexity for this problem?
easy
A. Perform a simple DFS traversal counting all nodes, which takes O(n) time.
B. Use the tree height to check if subtrees are perfect and recursively count nodes, achieving O((log n)^2) time.
C. Apply a greedy approach by counting nodes level by level until the last incomplete level.
D. Use a breadth-first search (BFS) traversal to count nodes, which is efficient for complete trees.

Solution

  1. Step 1: Understand the problem constraints

    The tree is complete, so the height can be used to identify perfect subtrees quickly.
  2. Step 2: Recognize the optimal approach

    Using the height to check if left or right subtree is perfect allows skipping large parts of the tree, reducing complexity to O((log n)^2).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Optimal approach leverages tree height and completeness [OK]
Hint: Use tree height to skip perfect subtrees [OK]
Common Mistakes:
  • Assuming BFS or simple DFS is optimal
  • Using greedy level counting without height checks
3. Given the following code snippet for checking if a binary tree is symmetric, what is the final return value when called with the tree root = TreeNode(1, TreeNode(2), TreeNode(2))?
from typing import Optional

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

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return t1 == t2
        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

root = TreeNode(1, TreeNode(2), TreeNode(2))
print(isSymmetric(root))  # What is the output?
easy
A. false
B. Raises an exception
C. null
D. true

Solution

  1. Step 1: Trace isMirror on root.left and root.right nodes with value 2

    Both nodes exist and have equal values, so recursion continues.
  2. Step 2: Recursively check left.left vs right.right and left.right vs right.left (both null)

    Since both pairs are null, isMirror returns true for these calls, so overall returns true.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Symmetric tree with equal child nodes returns true [OK]
Hint: Symmetric tree with equal children returns true [OK]
Common Mistakes:
  • Confusing null checks causing exceptions
  • Returning false prematurely on equal nodes
  • Misreading recursion base cases
4. Consider the following buggy code snippet for building a tree from inorder and postorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or runtime errors?
medium
A. Line creating root node with postorder[-1]
B. Line initializing inorder_index to 0
C. Line attaching node as right child
D. Line popping from stack inside while loop

Solution

  1. Step 1: Identify inorder_index initialization

    inorder_index should start at the last index (len(inorder) - 1) because postorder is processed from end to start.
  2. Step 2: Consequences of wrong initialization

    Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Correct inorder_index initialization is critical for stack popping logic [OK]
Hint: inorder_index must start at last index, not zero [OK]
Common Mistakes:
  • Wrong inorder_index initialization
  • Confusing postorder traversal direction
  • Incorrect stack popping conditions
5. The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.
def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1
    for _ in range(h - 1):
        mid = (left + right) // 2
        if idx < mid:  # Bug here
            root = root.left
            right = mid
        else:
            root = root.right
            left = mid + 1
    return root is not null
medium
A. Line with 'if idx < mid:'
B. Line with 'return root is not null'
C. Line with 'root = root.right'
D. Line with 'left, right = 0, 2**(h - 1) - 1'

Solution

  1. Step 1: Understand binary search condition

    The condition should be 'if idx <= mid' to correctly include mid index in left subtree.
  2. Step 2: Identify impact of bug

    Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Correct binary search must include mid index [OK]
Hint: Binary search must use <= to include mid index [OK]
Common Mistakes:
  • Using < instead of <= in binary search condition
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