The Tree That Lied: BST Invariants, Heaps, and Graph Representations

By FreePare Team · Wed Sep 02 2026 · 8 min read

Lab 4 of the 75-problem placement system

An ordered structure is useful only while its ordering invariant holds. A binary-search tree can look locally correct and still violate a bound inherited from an ancestor. A heap can have the right root and still contain a broken subtree. A graph traversal can visit the right vertices and still use the wrong representation for the workload.

This lab moves from local checks to global invariants.

Use the NIST Dictionary of Algorithms and Data Structures as the terminology baseline; implementation-specific promises are cited from the Java 25 API where they matter.

Learning contract

You will learn to:

• Define a BST's ordering and duplicate policy before coding;
• Validate inherited bounds and reason about balanced versus degenerate shapes;
• Distinguish sift operations from bottom-up heap construction;
• Apply a bounded heap to top-k and scheduling problems;
• Select an adjacency list or matrix from V, E, direction, and edge-query needs;
• Manage visited state for components and cycles;
• Pass a 75-minute mixed exit lab at 80% or higher.

Entry diagnostic

1. Why is checking only a node's children insufficient to validate a BST?

2. Where do duplicates go, if they are allowed?

3. What is the height of a BST built from already sorted values by naïve insertion?

4. Why is one heap insertion O(log n) but bottom-up build-heap Theta(n)?

5. For top k largest values, why keep a min-heap rather than a max-heap?

6. When is an adjacency matrix reasonable?

7. Why must directed-cycle detection distinguish "seen before" from "on the current path"?

8. In an undirected DFS, why is the parent edge not automatically a cycle?

Six correct: attempt the counterexamples first. Fewer than six: complete all traces.

1. BST invariants are inherited

Define the policy used in this article:

• every key in the left subtree is strictly less than the node key;
• every key in the right subtree is strictly greater;
• duplicates are rejected.

Different policies are possible, but they must be explicit and consistent across insertion, search, deletion, and validation.

The local-check trap

Consider this tree:

        10
       /  \
      5   15
       \
       12

12 > 5, so the local parent-child relation passes. The tree is still invalid because every value in the left subtree of 10 must be below 10.

Pass ancestor bounds downward:

final class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) { this.value = value; }
}

static boolean isValidBst(TreeNode root) {
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private static boolean valid(TreeNode node, long lowerExclusive, long upperExclusive) {
    if (node == null) return true;
    if (node.value <= lowerExclusive || node.value >= upperExclusive) return false;

    return valid(node.left, lowerExclusive, node.value)
            && valid(node.right, node.value, upperExclusive);
}

Using long bounds permits every int key, including Integer.MIN_VALUE and Integer.MAX_VALUE, without sentinel collision.

Shape controls operation cost

Search cost is Theta(h), where h is height.

• balanced shape: h = Theta(log n);
• sorted insertion into an unbalanced BST: h = Theta(n);
• duplicate-heavy input: behavior depends on the duplicate policy.

Do not call an arbitrary BST operation O(log n) without a balance assumption. Java's TreeMap documents guaranteed logarithmic basic operations because its implementation maintains a red-black tree, but a hand-written unbalanced BST has no such guarantee.

Test empty, one node, valid extremes, ancestor-bound violation, duplicate, left chain, and right chain.

2. A heap promises only parent priority

A binary min-heap stored in an array uses:

parent(i) = (i - 1) / 2
left(i)   = 2i + 1
right(i)  = 2i + 2

The heap is not globally sorted. It guarantees that each parent is no greater than its children, so the minimum is at the root.

Insert and sift up

Append the value at the next array position, then swap with its parent while the heap property is violated. The path length is at most the heap height, so insertion is O(log n).

Remove root and sift down

Move the last value to the root, shrink the logical size, and repeatedly swap with the smaller child. A common bug uses the old size after shrinking and reads the removed slot. Write the size transition before the loop.

Why build-heap is linear

Inserting n items one by one costs O(n log n). Bottom-up heap construction calls sift-down from the last internal node toward the root. Most nodes are close to the leaves and move only a small distance.

At most n/2^(h+1) nodes have height h, so total work is bounded by:

n * sum(h / 2^(h+1)) = Theta(n)

The distinction matters: a single sift-down is O(log n); the structured sum of all bottom-up sift-downs is Theta(n). Princeton's priority-queue material develops the heap representation and operations.

Top-k with a bounded min-heap

import java.util.PriorityQueue;

static java.util.List<Integer> largestK(int[] values, int k) {
    if (k < 0 || k > values.length) {
        throw new IllegalArgumentException("invalid k");
    }

    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int value : values) {
        if (heap.size() < k) {
            heap.add(value);
        } else if (k > 0 && value > heap.peek()) {
            heap.remove();
            heap.add(value);
        }
    }

    java.util.List<Integer> result = new java.util.ArrayList<>(heap);
    result.sort(java.util.Comparator.reverseOrder());
    return result;
}

Invariant: after processing a prefix, the heap contains its largest min(k, prefixLength) values, and the smallest retained value is at the root. Processing costs O(n log k); the final sort costs O(k log k); auxiliary space is O(k) excluding output.

Java's PriorityQueue specifies head semantics and logarithmic enqueue/dequeue. Iteration order is not sorted order.

Scheduling follow-up: if priorities tie, add a stable secondary key such as sequence number. Do not assume the priority queue preserves insertion order.

3. Graph representation is an algorithmic decision

Define the graph before choosing storage:

Vertices V:
Edges E:
Directed or undirected:
Weighted or unweighted:
Self-loops allowed:
Parallel edges allowed:
Primary operations:

Adjacency list versus matrix

For an undirected adjacency list, add both u -> v and v -> u. Decide whether parallel edges should remain separate. For weighted graphs, store an edge object, not only a neighbor ID.

record Edge(int to, long weight) {}

static java.util.List<java.util.List<Edge>> newGraph(int vertices) {
    java.util.List<java.util.List<Edge>> graph = new java.util.ArrayList<>(vertices);
    for (int i = 0; i < vertices; i++) {
        graph.add(new java.util.ArrayList<>());
    }
    return graph;
}

Components

To count undirected connected components, start a traversal from every unvisited vertex. Each start marks exactly one new component.

static int componentCount(java.util.List<java.util.List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    int components = 0;

    for (int start = 0; start < graph.size(); start++) {
        if (visited[start]) continue;
        components++;

        java.util.Deque<Integer> stack = new java.util.ArrayDeque<>();
        stack.push(start);
        visited[start] = true;

        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int next : graph.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    stack.push(next);
                }
            }
        }
    }
    return components;
}

Time is Theta(V + E) for an adjacency list because each vertex and stored edge is processed a constant number of times.

Cycle state differs by graph type

Undirected DFS: an edge to an already visited vertex is a cycle only when that vertex is not the current node's parent. Parallel edges require a more precise edge-ID policy.

Directed DFS: use three states.

• UNSEEN: never entered;
• ACTIVE: on the current DFS path;
• DONE: fully processed.

An edge to ACTIVE is a back edge and proves a directed cycle. An edge to DONE does not.

Iterative DFS must preserve the same enter/exit distinction; a simple boolean visited flag is insufficient for directed-cycle detection.

Problem batch: G01-G12

Exit lab

In 75 minutes:

1. validate a BST under an explicitly stated duplicate policy;

2. solve a top-k or scheduling problem and prove the heap invariant;

3. choose a graph representation and implement components or cycle detection.

Each task is worth 10 for policy/selection, invariant/proof, code, tests, and complexity. Pass at 24/30. An answer that calls bottom-up build-heap O(n log n) or treats every previously visited directed vertex as a cycle cannot pass until corrected and retested.

Tags: coding-interview-patterns, coding-fundamentals, coding-practice, computer-science-fundamentals, programming-fundamentals, effective-study-techniques, freshers-placement-guide, how-to-prepare-for-placements