Lesson 8 of 10 · 10 min

Trees, BSTs and heaps

Traverse trees in the right order, use the BST invariant properly, and know when a heap beats sorting.

The four traversals and when each is right

Pre-order visits the node before its children — use it when the parent must be processed first, as in serialisation or copying a tree.

In-order visits left, node, right. On a BST that produces ascending order, which makes it the tool for validation and for kth-smallest.

Post-order visits children before the node — use it when the answer depends on the subtrees, such as computing height, or when deleting nodes safely.

Level-order is BFS with a queue, and is the only one that groups nodes by depth.

Level order, with the levels kept separate

from collections import deque

def level_order(root):
    if not root:
        return []
    out, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):     # snapshot the size FIRST
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        out.append(level)
    return out

Note: Without snapshotting len(queue), the next level bleeds into the current one.

The BST invariant is global

A binary search tree requires every node in the left subtree to be smaller than the node — not just its direct child. This is the single most common tree mistake: checking only parent against child accepts trees that are not BSTs.

Two correct approaches: pass an allowed (low, high) range down and tighten it at each step, or do an in-order traversal and verify it is strictly increasing.

Heaps

A heap keeps the smallest (or largest) element instantly accessible while allowing O(log n) insertion and removal. It does not keep everything sorted — only the root is guaranteed.

Python's heapq is a min-heap. For a max-heap, push negated values, or push tuples of (-priority, tiebreaker, item).

Top-k without sorting everything

import heapq

def top_k(nums, k):
    heap = []
    for value in nums:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif value > heap[0]:              # heap[0] is the smallest kept
            heapq.heapreplace(heap, value) # one sift instead of pop + push
    return sorted(heap, reverse=True)

# O(n log k) and O(k) memory, versus O(n log n) to sort everything

Worth remembering

In-order traversal of a BST yields sorted values — that is the validity test.
Most tree problems are 'return something useful from each subtree'.
A size-k heap gives top-k in O(n log k), beating a full O(n log n) sort.

Test it now

Tree recursion and heap selection appear throughout the medium bank.

Medium DSA quiz →All levels