Practice Problems

Tree and heap questions are staples of coding interviews and online assessments. The four problems below each cover one classic pattern: traversal by level, using the BST property, a size-limited heap, and merging with a heap. Think about an approach first, then compare with the solution. All the code shares this Node definition.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

Problem 1. Largest value on each level

Given a binary tree, return a list with the largest key at each depth, from the root downward. An empty tree gives an empty list. For example, with root 4, children 9 and 2, and grandchildren 3, 5 and 7, the answer is [4, 9, 7].

Approach: grouping by depth points to a level-order traversal. Popping exactly "the current queue length" items at a time processes one level per round. Time is O(n); space is the size of the widest level.

from collections import deque


def level_maxima(root):
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        best = None
        for _ in range(len(queue)):        # only this level's nodes
            node = queue.popleft()
            best = node.key if best is None else max(best, node.key)
            queue.extend(c for c in (node.left, node.right) if c)
        result.append(best)
    return result


tree = Node(4, Node(9, Node(3), Node(5)), Node(2, None, Node(7)))
print(level_maxima(tree))  # [4, 9, 7]

Problem 2. Range sum in a BST

Given a binary search tree and two integers lo and hi, return the sum of all keys with lo <= key <= hi. Subtrees that are certainly out of range must not be visited.

Approach: prune with the BST property. If the current key is below lo, everything in its left subtree is smaller still, so skip it; if it is above hi, skip the right subtree. The number of visited nodes is roughly O(h + number of matching nodes). An explicit stack keeps deep trees safe.

def range_sum(root, lo, hi):
    total, stack = 0, [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if lo <= node.key <= hi:
            total += node.key
        if node.key > lo:          # the left side may still hold keys >= lo
            stack.append(node.left)
        if node.key < hi:          # the right side may still hold keys <= hi
            stack.append(node.right)
    return total


bst = Node(10, Node(5, Node(3), Node(7)), Node(15, None, Node(18)))
print(range_sum(bst, 6, 15))  # 7 + 10 + 15 = 32

Problem 3. K-th highest score, live

A game server receives scores one at a time. After each score, output the K-th highest score seen so far, or while fewer than K scores have arrived.