Practice Problems

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 4 Time to complete: ~30 minutes

Table of Contents

1. Maximum Depth of a Binary Tree
2. Level-Order Traversal as List-of-Lists
3. Kth Largest Element (Formalized)
4. Lowest Common Ancestor in a BST
5. Try It Yourself
6. Summary & Next Steps

1. Maximum Depth of a Binary Tree

Problem: Find the number of nodes on the longest root-to-leaf path (this is height + 1, in Chapter 1's terms).

def max_depth(node):
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))
    # O(n) time — visits every node once
    # O(h) space — the recursion call stack, bounded by height (Chapter 1)

Already introduced in Chapter 1 — repeated here because it's the simplest possible template for a huge family of tree problems: combine results from both children, add work for the current node. Nearly every recursive tree problem in this chapter follows this same shape.

2. Level-Order Traversal as List-of-Lists

Problem: Return the tree's values grouped by level, e.g. [[4], [2, 6], [1, 3, 5, 7]] for the sample tree from Chapter 2.

from collections import deque
 
def level_order_grouped(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)         # snapshot: exactly how many nodes are in THIS level
        level_values = []
        for _ in range(level_size):      # process exactly that many before moving to the next level
            node = queue.popleft()
            level_values.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(level_values)
    return result
    # O(n) time, O(w) space, where w is the tree's maximum width

The trick beyond Chapter 2's plain level-order: snapshot len(queue) before the inner loop starts. Since children get appended to the same queue during the loop, that snapshot is what correctly separates "this level" from "the next level" being built up simultaneously.

3. Kth Largest Element (Formalized)

Problem: Given an unsorted list, find the kth largest element (not the kth distinct value — duplicates count).

import heapq
 
def kth_largest(items, k):
    min_heap = items[:k]
    heapq.heapify(min_heap)               # O(k)
    for item in items[k:]:
        if item > min_heap[0]:
            heapq.heapreplace(min_heap, item)    # O(log k)
    return min_heap[0]                      # the root IS the kth largest
    # O(n log k) time, O(k) space

This is Chapter 4's "k largest elements" pattern, specialized: once you've maintained a min-heap of the top k elements seen so far, the heap's root — the smallest of that top-k group — is by definition the kth largest element overall.

4. Lowest Common Ancestor in a BST

Problem: Given a BST and two node values, find their lowest common ancestor (LCA) — the deepest node that has both as descendants.

Naive approach: find the path from root to each node, then compare paths — O(h) time but O(h) extra space for two stored paths.

BST-aware approach: use the ordering property (Chapter 3) to navigate directly, without ever building explicit paths:

def lowest_common_ancestor(root, p_value, q_value):
    current = root
    while current is not None:
        if p_value < current.value and q_value < current.value:
            current = current.left           # both targets are smaller — LCA must be in the left subtree
        elif p_value > current.value and q_value > current.value:
            current = current.right            # both targets are larger — LCA must be in the right subtree
        else:
            return current                        # values split (or match) here — this IS the LCA
    return None
    # O(h) time, O(1) space — no explicit paths needed

Why this works: as long as p and q are on the same side of current.value, the LCA must be further down on that side (the current node isn't "between" them, so it can't be their lowest common ancestor). The moment they split to different sides — or one of them is the current node — you've found the LCA, because this is the first node from which they diverge.

This is a clean example of Chapter 3's core lesson applied to a new problem: the BST ordering property turns what would otherwise require building full paths (as in a generic binary tree with no ordering) into a direct O(h), O(1)-space walk.

5. Try It Yourself

# (a) Given a binary tree (not necessarily a BST), find the LCA of two nodes.
#     Hint: without the ordering property, you can't navigate directly — you need
#     to search both subtrees and combine results, similar to max_depth's shape.
 
# (b) Given a BST, find the kth SMALLEST element (not largest).
#     Hint: Chapter 2's inorder traversal already visits BST nodes in sorted
#     order — you don't need a heap at all for this one.
 
# (c) Convert a sorted array into a height-BALANCED BST.
#     Hint: recursively pick the middle element as the root, then recurse on
#     the left and right halves — this directly prevents the skewed-tree
#     problem from Chapter 3.

6. Summary & Next Steps

Key Takeaways

• "Combine results from both children, add work for the current node" is the reusable template behind most recursive tree problems — you'll recognize it again and again.
• Grouping level-order output by level only requires snapshotting the queue's length before each level's inner loop.
• Recognizing when a problem's structure (BST ordering, sorted output from inorder) lets you skip an otherwise-necessary data structure (a heap, an explicit path list) is a recurring high-value skill.

Concept Check

1. What's the reusable recursive "shape" behind max_depth, and where else in this chapter does it reappear?
2. Why does the BST-aware LCA algorithm avoid building explicit root-to-node paths, while a general binary tree's LCA algorithm cannot?
3. Why does finding the kth smallest element in a BST not require a heap, while kth largest in an unsorted list does?

Next Module

→ Module 8: Hashing

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index