Balanced Binary Tree

▶

Steps

setup

Initialize stack and pointers

Start with an empty stack, set node pointer to root (3), last_visited to null, and an empty heights map.

💡 Initialization sets up the iterative traversal and storage for heights, preparing to explore the tree.

Line:

stack = []
node = root
last_visited = None
heights = {}

💡 The algorithm uses a stack to simulate recursion and a map to store subtree heights.

fill_row

Push root (3) and move to left child (9)

Node 3 is pushed onto the stack, then traversal moves to its left child node 9.

💡 Moving left first follows postorder traversal order: left subtree first.

Line:

if node:
    stack.append(node)
    node = node.left

💡 Stack grows as we go deeper left; node pointer moves down the left subtree.

fill_row

Push node 9 and move left (null)

Node 9 is pushed onto the stack, then traversal attempts to move left but finds null.

💡 Reaching a leaf's left child signals we must consider right child or process node.

Line:

if node:
    stack.append(node)
    node = node.left

💡 Traversal reaches bottom left leaf, preparing to backtrack.

compare

Peek stack top (9), check right child (null), process node 9

Peek at node 9 on stack; since right child is null, compute heights and check balance for node 9.

💡 Processing leaf node means calculating height and confirming balance immediately.

Line:

peek = stack[-1]
if peek.right and last_visited != peek.right:
    node = peek.right
else:
    left_height = heights.get(peek.left, 0)
    right_height = heights.get(peek.right, 0)
    if abs(left_height - right_height) > 1:
        return False
    heights[peek] = 1 + max(left_height, right_height)
    last_visited = stack.pop()

💡 Leaf node height is 1; no imbalance found here.

fill_row

Back to node 3, move to right child (20)

After processing left subtree, node pointer moves to right child 20 of root 3 to explore right subtree.

💡 Postorder requires visiting right subtree after left before processing node.

Line:

if peek.right and last_visited != peek.right:
    node = peek.right

💡 Traversal continues down right subtree, stack still holds node 3.

fill_row

Push node 20 and move to left child (15)

Node 20 is pushed onto the stack, then traversal moves to its left child node 15.

💡 Continuing postorder, we explore left subtree of node 20 first.

Line:

if node:
    stack.append(node)
    node = node.left

💡 Stack now contains nodes 3 and 20, traversal goes deeper left.

fill_row

Push node 15 and move left (null)

Node 15 is pushed onto the stack, then traversal attempts to move left but finds null.

💡 Reached leaf node 15's left child, preparing to backtrack or explore right child.

Line:

if node:
    stack.append(node)
    node = node.left

💡 Traversal reaches leaf node bottom again.

compare

Process node 15 (leaf)

Peek at node 15; no right child to visit, so compute height and check balance for node 15.

💡 Leaf node height is 1; no imbalance here.

Line:

peek = stack[-1]
if peek.right and last_visited != peek.right:
    node = peek.right
else:
    left_height = heights.get(peek.left, 0)
    right_height = heights.get(peek.right, 0)
    if abs(left_height - right_height) > 1:
        return False
    heights[peek] = 1 + max(left_height, right_height)
    last_visited = stack.pop()

💡 Height of node 15 is 1, stored for parent calculations.

fill_row

Move to right child of 20 (node 7)

After processing left child 15, traversal moves to right child 7 of node 20.

💡 Postorder requires visiting right subtree before processing node 20.

Line:

if peek.right and last_visited != peek.right:
    node = peek.right

💡 Traversal continues down right subtree of node 20.

fill_row

Push node 7 and move left (null)

Node 7 is pushed onto the stack, then traversal attempts to move left but finds null.

💡 Reached leaf node 7's left child, preparing to backtrack or explore right child.

Line:

if node:
    stack.append(node)
    node = node.left

💡 Traversal reaches leaf node bottom again.

compare

Process node 7 (leaf)

Peek at node 7; no right child to visit, so compute height and check balance for node 7.

💡 Leaf node height is 1; no imbalance here.

Line:

peek = stack[-1]
if peek.right and last_visited != peek.right:
    node = peek.right
else:
    left_height = heights.get(peek.left, 0)
    right_height = heights.get(peek.right, 0)
    if abs(left_height - right_height) > 1:
        return False
    heights[peek] = 1 + max(left_height, right_height)
    last_visited = stack.pop()

💡 Height of node 7 is 1, stored for parent calculations.

compare

Process node 20 after children

Peek at node 20; both children processed, compute heights and check balance for node 20.

💡 Height difference between left (1) and right (1) is 0, so balanced.

Line:

left_height = heights.get(peek.left, 0)
right_height = heights.get(peek.right, 0)
if abs(left_height - right_height) > 1:
    return False
heights[peek] = 1 + max(left_height, right_height)
last_visited = stack.pop()

💡 Height of node 20 is 2, stored for parent calculations.

compare

Process root node 3 after children

Peek at root node 3; both children processed, compute heights and check balance for root.

💡 Height difference between left (1) and right (2) is 1, which is allowed.

Line:

left_height = heights.get(peek.left, 0)
right_height = heights.get(peek.right, 0)
if abs(left_height - right_height) > 1:
    return False
heights[peek] = 1 + max(left_height, right_height)
last_visited = stack.pop()

💡 Height of root is 3; tree is balanced.

reconstruct

Traversal complete, return true

Stack is empty and no imbalance found, so the function returns true indicating the tree is balanced.

💡 No height difference exceeded 1, confirming balanced tree property.

Line:

return True

💡 Algorithm successfully verified balance by bottom-up height checks.

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

def isBalanced(root):
    if not root:
        return True  # STEP 1
    stack = []  # STEP 1
    node = root  # STEP 1
    last_visited = None  # STEP 1
    heights = {}  # STEP 1
    while stack or node:  # STEP 2-13
        if node:  # STEP 2,3,6,7,10
            stack.append(node)  # STEP 2,3,6,7,10
            node = node.left  # STEP 2,3,6,7,10
        else:
            peek = stack[-1]  # STEP 4,8,11,12,13
            if peek.right and last_visited != peek.right:  # STEP 5,9
                node = peek.right  # STEP 5,9
            else:
                left_height = heights.get(peek.left, 0)  # STEP 4,8,11,12,13
                right_height = heights.get(peek.right, 0)  # STEP 4,8,11,12,13
                if abs(left_height - right_height) > 1:  # STEP 4,8,11,12,13
                    return False  # STEP 4,8,11,12,13
                heights[peek] = 1 + max(left_height, right_height)  # STEP 4,8,11,12,13
                last_visited = stack.pop()  # STEP 4,8,11,12,13
    return True  # STEP 14

if __name__ == '__main__':
    root = TreeNode(3)  # Setup tree
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(isBalanced(root))  # Expected: True

📊

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.

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. You need to output all nodes of a binary tree such that each node is processed only after its left and right children have been processed. Which traversal approach guarantees this order?

easy

A. Postorder traversal using depth-first search

B. Preorder traversal using recursion

C. Level-order traversal using a queue

D. Inorder traversal using recursion

Solution

1. Step 1: Understand traversal order requirements

   Postorder traversal processes left subtree, then right subtree, then the node itself, ensuring children are processed before the parent.

2. Step 2: Compare with other traversals

   Preorder and inorder do not guarantee children processed before parent; level-order processes nodes by depth, not child-first.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Postorder traversal matches the problem's processing order [OK]

Hint: Postorder processes children before parent [OK]

Common Mistakes:

• Confusing inorder with postorder
• Thinking preorder processes children first

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. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 5: rob_current calculation uses left[0] and right[0]

B. Line 7: Returning (rob_current, not_rob_current)

C. Line 6: not_rob_current uses max(left) + max(right)

D. Line 2: Base case returns (0, 0)

Solution

1. Step 1: Understand rob_current calculation

   rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.

2. Step 2: Identify the bug

   Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using rob values of children overcounts and breaks correctness [OK]

Hint: Rob current node + not_rob children, not rob children [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple
• Forgetting adjacency constraints

4. What is the space complexity of the optimal recursive approach to invert a binary tree, assuming the tree has n nodes and height h?

medium

A. O(n) because each node's children pointers are swapped individually

B. O(n) due to storing all nodes in a queue during traversal

C. O(1) because inversion is done in-place without extra data structures

D. O(h) due to recursion stack depth proportional to tree height

Solution

1. Step 1: Identify auxiliary space usage in recursion

   The algorithm uses recursion, so the call stack depth is proportional to the height h of the tree.

2. Step 2: Distinguish between in-place operations and recursion stack

   Swapping pointers is in-place (O(1) per node), but recursion stack space is O(h), not O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack dominates space, proportional to tree height h [OK]

Hint: Recursion stack space depends on tree height, not node count [OK]

Common Mistakes:

• Confusing in-place operation with O(1) total space
• Assuming queue-based BFS space applies to recursive DFS
• Counting node swaps as extra space

5. Suppose the binary tree nodes have parent pointers already, but the tree is very deep (height h). You want to find the Lowest Common Ancestor of two nodes p and q. Which approach is best to optimize time and space, and why?

hard

A. Use brute force by checking all ancestors of p and q repeatedly until common ancestor is found.

B. Use the parent pointer + ancestor set approach, building a set for p's ancestors and then traversing q's ancestors.

C. Use recursive DFS from root to find paths to p and q, then compare paths to find LCA.

D. Use the parent pointer + two-pointer technique: move the deeper node up until both nodes are at the same depth, then move both up simultaneously until they meet.

Solution

1. Step 1: Understand problem constraints

   Nodes have parent pointers, tree is deep, so space usage matters.

2. Step 2: Evaluate approaches

   Ancestor set approach (B) uses O(h) space. Recursive DFS (C) and brute force (D) are inefficient for deep trees.

3. Step 3: Two-pointer technique

   Moving deeper node up to equalize depth, then moving both up simultaneously uses O(1) space and O(h) time, optimal for deep trees.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Two-pointer approach optimizes space and time for deep trees with parent pointers [OK]

Hint: Two-pointer approach uses O(1) space for LCA with parent pointers [OK]

Common Mistakes:

• Using ancestor sets unnecessarily
• Recursing from root wasting time
• Brute force repeated ancestor checks