Balanced Binary Tree - Watch the Algorithm Execute, Step by Step
Watching each stack operation and height calculation reveals how the algorithm ensures balance without recursion, making the process clear and intuitive.
Step 1/14
·Active fill★Answer cell
Current node: 1
3920157
Current node: 2
3920157
3920157
3920157
Current node: 3
3920157
Current node: 4
3920157
3920157
3920157
Current node: 5
3920157
3920157
3920157
3920157
3920157
3920157
Return: true
Key Takeaways
✓ The algorithm uses an iterative postorder traversal with a stack to compute subtree heights bottom-up.
This approach avoids recursion and shows how stack and pointers simulate call stack behavior.
✓ Height information is stored in a map keyed by nodes, enabling quick balance checks at each node.
Tracking heights explicitly clarifies how balance depends on subtree heights, not just structure.
✓ The traversal carefully decides when to move right or process a node, ensuring children are processed before parents.
This decision logic is key to postorder traversal and is visually clear when watching stack and node pointer changes.
Practice
(1/5)
1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?
easy
A. Postorder traversal using two stacks
B. Level-order traversal using a queue
C. Morris preorder traversal using threaded binary tree
D. Inorder traversal using recursion
Solution
Step 1: Understand traversal order requirement
The problem requires visiting root before left and right subtrees, which is preorder traversal.
Step 2: Identify approach with no extra space
Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.
Final Answer:
Option C -> Option C
Quick Check:
Preorder visits root first; Morris traversal achieves this with O(1) space [OK]
Hint: Preorder visits root before children [OK]
Common Mistakes:
Confusing inorder or postorder with preorder traversal
Assuming recursion is always needed
Using level-order which visits nodes by depth
2. Consider the following iterative postorder traversal code to compute the diameter of a binary tree. Given the tree:
1
/ \
2 3
/
4
What is the final value of the variable diameter after the function completes?
easy
A. 2
B. 4
C. 1
D. 3
Solution
Step 1: Trace heights and diameter updates for each node.
The diameter is the maximum sum of left and right heights at any node, which is 3 edges, so the longest path length is 3 edges.
Final Answer:
Option D -> Option D
Quick Check:
Longest path is from node 4 to node 3 with length 3 edges [OK]
Hint: Diameter counts edges, not nodes [OK]
Common Mistakes:
Confusing diameter as number of nodes
Off-by-one in height calculation
Missing right subtree height
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. Examine the following buggy iterative DFS code for finding all root-to-leaf paths with a given sum. Which line contains the subtle bug that causes incorrect results?
def pathSum(root, targetSum):
if not root:
return []
res = []
stack = [(root, [root.val], root.val)]
while stack:
node, path, current_sum = stack.pop()
if current_sum == targetSum:
res.append(path)
if node.right:
stack.append((node.right, path + [node.right.val], current_sum + node.right.val))
if node.left:
stack.append((node.left, path + [node.left.val], current_sum + node.left.val))
return res
medium
A. Line appending left child to stack
B. Line initializing stack with root node and path
C. Line appending right child to stack
D. Line checking if current_sum == targetSum without verifying leaf node
Solution
Step 1: Identify condition for adding path to results
Correct code adds path only if current node is leaf and sum matches.
Step 2: Locate bug
Here, path is added whenever sum matches, regardless of leaf status, causing incomplete paths to be included.
Final Answer:
Option D -> Option D
Quick Check:
Missing leaf check causes incorrect paths in results [OK]
Hint: Always check leaf node before adding path [OK]
Common Mistakes:
Adding path before confirming leaf node
Forgetting to backtrack in recursion
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
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.
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.
Final Answer:
Option D -> Option D
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 unknownstrongwhile earning +1 Grip toward your certificate.