Invert Binary Tree

▶

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.

traverse

Recurse on Left Subtree of Node 4

The algorithm moves to the left child of node 4, which is node 2, pushing it onto the call stack as entered to process its subtrees.

💡 Recursion dives into the left subtree first, following postorder traversal order.

Line:

invertTree(root.left)

💡 The left subtree must be inverted before swapping children at node 4.

traverse

Recurse on Left Subtree of Node 2

The algorithm moves to the left child of node 2, which is node 1, pushing it onto the call stack as entered to process its subtrees.

💡 Continuing recursion down the left subtree to reach leaf nodes first.

Line:

invertTree(root.left)

💡 Leaf nodes will be reached first, where recursion will start returning.

traverse

Recurse on Left Subtree of Node 1 (Null)

Node 1 has no left child (null), so the recursion returns null immediately for this subtree.

💡 Base case reached: null nodes return immediately, stopping recursion down that path.

Line:

if root is null:
    return null

💡 Null children mark the end of recursion branches.

traverse

Recurse on Right Subtree of Node 1 (Null)

Node 1 has no right child (null), so the recursion returns null immediately for this subtree as well.

💡 Both children of leaf node 1 are null, so recursion returns back to node 1 for swapping.

Line:

if root is null:
    return null

💡 Leaf nodes have no children to invert, so recursion returns to parent.

expand

Swap Children of Node 1

Both children of node 1 are null, so swapping left and right children has no visible effect. The algorithm swaps them in-place and prepares to return node 1.

💡 Swapping children at leaf nodes is trivial but necessary to maintain uniform logic.

Line:

root.left, root.right = root.right, root.left
return root

💡 Swapping at leaf nodes confirms the base case returns the node unchanged.

traverse

Recurse on Right Subtree of Node 2

Back at node 2, the algorithm now recurses into its right child, node 3, pushing it onto the call stack to invert its subtrees.

💡 After finishing left subtree, recursion proceeds to right subtree before swapping at node 2.

Line:

invertTree(root.right)

💡 Both subtrees must be inverted before swapping children at the current node.

traverse

Recurse on Left and Right Subtrees of Node 3 (Leaf Nodes)

The algorithm recursively processes node 3's children: left child 6 and right child 9, both leaf nodes, reaching base cases and returning.

💡 Recursion reaches leaf nodes 6 and 9, which have no children to invert.

Line:

invertTree(root.left)
invertTree(root.right)

💡 Leaf nodes return themselves after swapping null children.

expand

Swap Children of Node 6 (Leaf)

Node 6 has no children, so swapping left and right children has no effect. The algorithm swaps them and returns node 6.

💡 Swapping children at leaf nodes is trivial but necessary for uniformity.

Line:

root.left, root.right = root.right, root.left
return root

💡 Leaf nodes return themselves unchanged after swapping.

expand

Swap Children of Node 9 (Leaf)

Node 9 has no children, so swapping left and right children has no effect. The algorithm swaps them and returns node 9.

💡 Leaf node 9 is processed similarly to node 6, returning itself after swapping.

Line:

root.left, root.right = root.right, root.left
return root

💡 Leaf nodes consistently return themselves after swapping children.

expand

Swap Children of Node 3

After both children of node 3 are inverted, the algorithm swaps node 3's left and right children in-place, changing left from 6 to 9 and right from 9 to 6.

💡 Swapping children at internal nodes changes the tree structure progressively.

Line:

root.left, root.right = root.right, root.left
return root

💡 Swapping children at node 3 inverts its subtree structure.

expand

Swap Children of Node 2

After both children of node 2 are inverted, the algorithm swaps node 2's left and right children in-place, changing left from 1 to 3 and right from 3 to 1.

💡 Swapping children at node 2 continues the inversion up the tree.

Line:

root.left, root.right = root.right, root.left
return root

💡 Swapping children at node 2 inverts its subtree structure.

traverse

Recurse on Right Subtree of Node 4

Back at the root node 4, the algorithm now recurses into its right child, node 7, pushing it onto the call stack to invert its subtrees.

💡 After finishing left subtree, recursion proceeds to right subtree before swapping at root.

Line:

invertTree(root.right)

💡 Both subtrees must be inverted before swapping children at the root.

expand

Swap Children of Root Node 4

After both left and right subtrees of root node 4 are inverted, the algorithm swaps its left and right children in-place, changing left from 2 to 3 and right from 3 to 2.

💡 Swapping children at the root completes the full tree inversion.

Line:

root.left, root.right = root.right, root.left
return root

💡 Swapping children at root finalizes the inversion of the entire tree.

reconstruct

Return Final Inverted Tree Root

The recursion completes and returns the root node of the fully inverted tree. The tree structure now reflects the inversion with left and right children swapped at every node.

💡 Returning the root signals completion of the inversion process.

Line:

return root

💡 The returned root represents the entire inverted tree.

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

def invertTree(root):
    # STEP 1: Base case - if node is null, return null
    if root is null:
        return null
    # STEP 2: Recurse on left subtree
    invertTree(root.left)
    # STEP 3: Recurse on right subtree
    invertTree(root.right)
    # STEP 4: Swap left and right children
    root.left, root.right = root.right, root.left
    # STEP 5: Return current node
    return root

# Example usage:
# root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, TreeNode(6), TreeNode(9)))
# inverted_root = invertTree(root)

📊

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.

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. You are given a binary tree and two nodes within it. You need to find the node that is the deepest common ancestor of both nodes. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Use a brute force approach by finding paths from root to each node and then comparing the paths.

B. Build a parent pointer map for all nodes, then use ancestor sets to find the lowest common ancestor.

C. Apply a greedy algorithm that picks the first common node found during a preorder traversal.

D. Use dynamic programming to store results of subtrees and combine them to find the ancestor.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the lowest common ancestor efficiently, ideally in O(n) time and O(n) space.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but less optimal. Greedy (C) fails because it may pick incorrect ancestors. DP (D) is not applicable here. Building parent pointers and using ancestor sets (B) provides an optimal and clean solution.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Parent pointer + ancestor set approach is standard optimal solution [OK]

Hint: Parent pointers + ancestor sets yield optimal LCA solution [OK]

Common Mistakes:

• Assuming greedy traversal finds correct LCA
• Using DP where not applicable
• Brute force is optimal

2. You need to convert a binary tree into a string and then reconstruct the exact same tree from that string. Which approach guarantees that the tree structure, including null children, is preserved and can be reconstructed efficiently?

easy

A. Use level order traversal (BFS) including null markers for missing children, then deserialize by reading nodes level by level.

B. Use a greedy traversal that records only node values without null markers, then reconstruct by inserting nodes in order.

C. Use dynamic programming to store subtree encodings and reconstruct from stored subtrees.

D. Use inorder traversal without null markers and reconstruct by assuming a balanced tree.

Solution

1. Step 1: Understand the need for null markers

   Without null markers, the tree structure cannot be uniquely reconstructed because missing children are ambiguous.

2. Step 2: Recognize BFS with null markers preserves structure

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

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Level order with null markers uniquely encodes tree structure [OK]

Hint: Null markers are essential to preserve tree shape [OK]

Common Mistakes:

• Ignoring null markers leads to ambiguous deserialization
• Assuming inorder traversal alone can reconstruct arbitrary trees
• Using greedy or DP approaches that don't preserve structure

3. Given a binary tree where each root-to-leaf path represents a number formed by concatenating node values, which algorithmic approach guarantees computing the sum of all such numbers efficiently without missing any path or double counting partial paths?

easy

A. Depth-first search (DFS) that accumulates the current number along the path and adds it only at leaf nodes

B. Dynamic programming that stores sums for subtrees and combines them at the root

C. Greedy traversal that sums node values at each level independently

D. Breadth-first search (BFS) that sums values of nodes at each depth and multiplies by depth

Solution

1. Step 1: Understand problem requirements

   The problem requires summing numbers formed by concatenating node values from root to leaf, so partial paths must not be summed prematurely.

2. Step 2: Identify correct traversal pattern

   DFS naturally explores root-to-leaf paths, allowing accumulation of the current number and summing only at leaf nodes, ensuring correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS accumulates path values correctly and sums only at leaves [OK]

Hint: Sum only at leaves during DFS traversal [OK]

Common Mistakes:

• Summing at non-leaf nodes
• Using BFS without path tracking

4. What is the time complexity of the Morris preorder traversal algorithm on a binary tree with n nodes, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because each node is visited multiple times during threading

B. O(n) but with O(n) auxiliary space due to recursion stack

C. O(n^2) because the inner loop to find predecessor can traverse many nodes repeatedly

D. O(n) because each edge is traversed at most twice during threading and restoration

Solution

1. Step 1: Identify traversal of nodes and edges

   Each node is visited once, and each edge is traversed at most twice (once to create thread, once to remove it).

2. Step 2: Explain why complexity is linear

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

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Threading and restoring links cause at most two visits per edge [OK]

Hint: Each edge visited max twice -> O(n) time [OK]

Common Mistakes:

• Assuming inner loop causes O(n^2)
• Confusing threading with recursion stack space
• Thinking threading causes log n overhead

5. Suppose the Path Sum problem is modified so that node values can be negative, and you want to find if any root-to-leaf path sums exactly to targetSum. Which of the following changes to the DFS approach is necessary to handle this correctly?

hard

A. Precompute all path sums and store them in a hash set for O(1) lookup

B. Add memoization to avoid revisiting nodes with the same current sum

C. Use BFS instead of DFS to guarantee shortest path sum

D. Remove early stopping because negative values can invalidate pruning assumptions

Solution

1. Step 1: Understand impact of negative values

   Negative values mean partial sums can decrease later, so pruning based on current sum is unsafe.

2. Step 2: Adjust algorithm accordingly

   Early stopping based on partial sums must be removed to avoid missing valid paths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Negative values break pruning assumptions, so early stopping must be disabled [OK]

Hint: Negative values invalidate pruning, so no early stopping [OK]

Common Mistakes:

• Assuming early stopping always works
• Switching to BFS unnecessarily