Binary Trees & BST

Tree Terminology

A tree is a set of nodes connected by edges, with one node designated the root and no cycles. In a binary tree each node has at most two children, called left and right.

Root, Leaves, Depth, Height

• Root — the top node, the only node without a parent.
• Leaf — a node with no children.
• Depth of a node — the number of edges from the root to it (the root has depth 0).
• Height of a tree — the number of levels, i.e. the depth of the deepest node plus one. Conventions differ (some count edges); these lessons count levels, so an empty tree has height 0 and a single node height 1.
• Subtree — any node together with all of its descendants. Every subtree is itself a tree, which is why recursion fits trees so well.

Tree Shapes

Shape determines cost, because most tree operations walk one path from the root, and the longest path is the height.

Traversals

A traversal visits every node exactly once, so it is O(n). What differs is the order, and each order suits different tasks. The demo runs all of them on the same tree and prints it sideways: 24_tree_traversals.go.

Depth-First Orders

The three depth-first orders are the same three lines of code in a different order. The nil check is the base case: an empty subtree contributes nothing.

type Node struct {
	Val         int
	Left, Right *Node
}

// in-order: left subtree, node, right subtree.
// On a binary search tree this visits keys in sorted order.
func inOrder(n *Node, visit func(int)) {
	if n == nil {
		return
	}
	inOrder(n.Left, visit)
	visit(n.Val)
	inOrder(n.Right, visit)
}

// pre-order  (node, left, right): copy or serialize a tree top-down.
// post-order (left, right, node): compute answers bottom-up, free a tree.

Iterative Traversal

Converting recursion to an explicit stack (Phase 1) makes the traversal pausable — the basis of iterators over ordered maps. For in-order: descend left as far as possible, pushing each node; when you cannot go further, pop a node, visit it, and continue with its right subtree.

func inOrderIter(root *Node) []int {
	var out []int
	var stack []*Node
	cur := root
	for cur != nil || len(stack) > 0 {
		for cur != nil { // go left, remembering the path back
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		out = append(out, cur.Val)
		cur = cur.Right // then the right subtree
	}
	return out
}

Level Order

Level-order traversal visits the tree row by row using a FIFO queue — breadth-first search, which Phase 3 generalizes to graphs. Processing the queue in batches of its current length separates the levels.

func levelOrder(root *Node) [][]int {
	var levels [][]int
	if root == nil {
		return levels
	}
	queue := []*Node{root}
	for len(queue) > 0 {
		width := len(queue) // nodes on this level
		var level []int
		for i := 0; i < width; i++ {
			n := queue[0]
			queue = queue[1:]
			level = append(level, n.Val)
			if n.Left != nil {
				queue = append(queue, n.Left)
			}
			if n.Right != nil {
				queue = append(queue, n.Right)
			}
		}
		levels = append(levels, level)
	}
	return levels
}

Thinking in Subtrees

Nearly every binary-tree problem yields to one question: if I already had the answers for the left and right subtrees, how would I combine them into the answer for this node? This is the recursive leap of faith from Phase 1, applied to two sub-problems at once. The demo solves six problems this way: 26_tree_problems.go.

Bottom-Up Answers

Height is the simplest example: height(node) = 1 + max(height(left), height(right)). Some problems need a different value returned than the one asked. The diameter — the longest path between any two nodes — passes through some node and uses the depths of its two subtrees. The function returns depth, which the parent needs, and records the best diameter on the side.

// diameter returns the number of edges on the longest path in the tree.
func diameter(root *Node) int {
	best := 0
	var depth func(n *Node) int
	depth = func(n *Node) int {
		if n == nil {
			return 0
		}
		l, r := depth(n.Left), depth(n.Right)
		best = max(best, l+r) // the longest path that bends at n
		return 1 + max(l, r)  // what the parent needs
	}
	depth(root)
	return best
}

Top-Down Parameters

Other problems pass information down. To check for a root-to-leaf path with a given sum, subtract each node's value from the target on the way down; at a leaf, the remaining target must be zero. The same pattern checks that a tree is a valid BST by passing down the allowed range of keys.

Lowest Common Ancestor

The lowest common ancestor of two nodes is the deepest node that has both as descendants. Search both subtrees: if one target is found on each side, the current node is where their paths meet; otherwise the answer is whatever the one successful side returned. The whole tree is visited at most once — O(n).

Binary Search Trees

A binary search tree (BST) adds an ordering rule: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. Each comparison therefore discards an entire subtree, like binary search on a sorted slice — but the tree also supports fast insertion and deletion.

Searching for 7 compares against one node per level: 8 (go left), 3 (go right), 6 (go right), 7 (found). The cost is the height of the tree, not the number of nodes.

Search and Insert

Search walks down one path. Insert searches for the key and, on reaching an empty spot, places a new leaf there. Writing insert as a recursive function that returns the (possibly new) subtree root lets each parent re-attach its child with one assignment, with no special case for an empty tree. cmp.Ordered (Go 1.21) lets the same code handle integers, floats, and strings.

func insert[K cmp.Ordered](n *node[K], k K) *node[K] {
	if n == nil {
		return &node[K]{key: k} // empty spot: the new leaf goes here
	}
	switch {
	case k < n.key:
		n.left = insert(n.left, k)
	case k > n.key:
		n.right = insert(n.right, k)
	} // equal keys: already present, a set stores each key once
	return n
}

Deletion

Deletion has three cases, and the third is the one worth understanding:

1. Leaf — remove it.
2. One child — the child takes the node's place.
3. Two children — copy the in-order successor (the smallest key in the right subtree) into the node, then delete the successor from the right subtree. The successor has no left child, so that second deletion is case 1 or 2, and the ordering rule still holds because the successor is larger than everything on the left and smaller than everything else on the right.

Ordered Queries

A hash map finds exact keys faster than a BST, but it knows nothing about order. A BST also answers minimum and maximum, "smallest key ≥ x" (ceiling), range queries, and sorted iteration — each in O(h) or O(h + results). The demo implements all of them, plus a validity check, on a generic ordered set: 25_binary_search_tree.go.

Shape Decides Speed

Every BST operation costs O(h). If keys arrive in random order, the expected height is O(log n); in the demo, 2,000 random keys produce a height in the low twenties. If keys arrive sorted, each new key becomes the right child of the previous one and the tree degenerates into a linked list of height 2,000. Self-balancing trees (AVL, red-black) rotate nodes after updates to guarantee O(log n) height; they are covered in Advanced Trees.

Common Pitfalls

Tree code is short and recursive, so its mistakes are usually in what is compared or returned.

Validating a BST Locally

Checking only left.key < node.key < right.key at each node is wrong: a grandchild can sit on the wrong side of its grandparent while every parent–child pair looks fine. Pass the allowed (low, high) range down the tree, or check that an in-order traversal is strictly increasing.

Discarding the Returned Subtree

With the "return the new subtree root" style, calling insert(n.left, k) without assigning the result to n.left silently loses the new node. Every recursive call that can change the tree must have its result stored.

Recursion Depth on Degenerate Trees

Recursive traversal uses stack space proportional to the height. On a balanced tree that is tiny; on a degenerate tree built from millions of sorted keys it is millions of frames. Balance the tree, or use the iterative traversals.

Practice Lab

For each exercise, first write down what the recursive call returns and how a node combines its children's results.

Run the Demos

1. In 25_binary_search_tree.go, insert the 2,000 keys in the order 1000, 500, 1500, 250, 750, … (always the middle of the remaining range). What height do you get, and why is it the best possible?
2. In 26_tree_problems.go, replace isBalanced with a version that calls maxDepth at every node and count the calls on a degenerate tree of 1,000 nodes.

Exercises

1. Kth smallest. Return the k-th smallest key of a BST by stopping an in-order traversal early.
2. Build from sorted. Build a height-balanced BST from a sorted slice by choosing the middle element as the root, recursively.
3. Right side view. Return the last value of each level (what you see looking at the tree from the right).
4. Rebuild from traversals. Reconstruct a tree from its pre-order and in-order sequences (values are distinct).

Next lesson: Heaps & Priority Queues.