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.
💡 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.
💡 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.
💡 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.
💡 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.
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
Step 1: Understand traversal order requirement
Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
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.
Final Answer:
Option C -> Option C
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
Step 1: Understand the problem constraints
The tree is complete, so the height can be used to identify perfect subtrees quickly.
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).
Final Answer:
Option B -> Option B
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
Step 1: Trace isMirror on root.left and root.right nodes with value 2
Both nodes exist and have equal values, so recursion continues.
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.
Final Answer:
Option D -> Option D
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
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.
Step 2: Consequences of wrong initialization
Starting at 0 causes incorrect comparisons and popping logic, leading to wrong tree structure or runtime errors.
Final Answer:
Option B -> Option B
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
Step 1: Understand binary search condition
The condition should be 'if idx <= mid' to correctly include mid index in left subtree.
Step 2: Identify impact of bug
Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.
Final Answer:
Option A -> Option A
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 unknownstrongwhile earning +1 Grip toward your certificate.