Back to the course
Data Structures & Algorithms · Module 07 of 10

Trees

Hierarchies, recursion, traversals, and binary search trees.

Build
Binary search tree with delete
Solve
Traversals, validation, balance, LCA
The finish line — what go test shows once every exercise in this module passes
$ go test -v ./07-trees/ | grep '^--- ' --- PASS: TestBSTInsertContains (0.00s) --- PASS: TestBSTDelete (0.00s) --- PASS: TestBSTRandomized (0.00s) --- PASS: TestTraversals (0.00s) --- PASS: TestLevelOrder (0.00s) --- PASS: TestMaxDepth (0.00s) --- PASS: TestIsValidBST (0.00s) --- PASS: TestIsBalanced (0.00s) --- PASS: TestInvert (0.00s) --- PASS: TestLCA (0.00s)
Module 7 · tests 10
WHY

Why it matters.

Trees model anything hierarchical: file systems, the DOM, org charts, syntax trees in a compiler, JSON. Binary search trees keep data sorted while supporting fast insert and lookup, and their balanced cousins are everywhere — SQLite and most databases index tables with B-trees, and many languages' sorted maps are red-black trees.

Trees are also where recursion stops being a party trick and becomes the natural way to think.

IDEAS

The core ideas.

Vocabulary. A root at the top; each node has children; nodes with none are leaves. Depth counts edges down from the root; height is the longest path down to a leaf. In a binary tree every node has at most two children.

The recursive shape. Nearly every tree function looks like this:

  1. If the node is nil, return the base answer.
  2. Recurse into Left and Right.
  3. Combine their answers with the node's own value.

Max depth, size, sum, "is it balanced", "invert it" — all the same three lines with different combine steps.

Traversals. Depth-first visits come in three orders, named by when the node itself is visited: pre-order (node, left, right), in-order (left, node, right), and post-order (left, right, node). Breadth-first (level-order) uses a queue to visit one level at a time.

Binary search tree. For every node, everything in the left subtree is smaller and everything in the right is larger. Search, insert, and delete each walk one root-to-leaf path: O(h). In-order traversal of a BST yields its values sorted.

Balance. A BST's height depends on insertion order. Random inserts give about log₂ n; inserting already-sorted data gives a chain of height n — a linked list in disguise. Self-balancing trees (AVL, red-black) rotate nodes to keep h = O(log n) no matter what.

COST

Cost of operations.

Operation (BST)BalancedDegenerate
Search / insert / deleteO(log n)O(n)
Min / maxO(log n)O(n)
Traverse allO(n)O(n)
IN GO

Go specifics.

  • No built-in tree type. You define TreeNode with Left, Right *TreeNode; a nil pointer is an empty subtree.
  • Recursive closures need declaring first: var walk func(*TreeNode); walk = func(n *TreeNode) { … walk(n.Left) … }. That pattern lets the closure capture an output slice.
  • Pointer-to-pointer insert. Walking a **TreeNode (link := &t.root) lets you fill in the nil child directly, with no "is the tree empty?" special case — the same trick as Module 3.
  • Iterators (Go 1.23+). A traversal can be exposed as iter.Seq[int] so callers can for v := range tree.All() and stop early. Try it after the exercises.
EXAMPLE

Worked example: root-to-leaf path sum.

Does any root-to-leaf path add up to target? Not an exercise, but it's the recursive shape exactly:

func hasPathSum(n *TreeNode, target int) bool {
	if n == nil {
		return false // 1. base case
	}
	if n.Left == nil && n.Right == nil {
		return n.Val == target // a leaf: does this path finish on target?
	}
	rest := target - n.Val // 2. recurse with what's left
	return hasPathSum(n.Left, rest) || hasPathSum(n.Right, rest) // 3. combine
}
PATTERNS

Patterns to recognize.

  • Bottom-up recursion — heights, balance, diameter: children report up, parent combines.
  • Top-down with bounds — validating a BST: pass the allowed (low, high) range down.
  • BST navigation — use the ordering to choose one side (search, LCA, floor/ceiling).
  • Level-order BFS — anything "per level": averages, right-side view, zigzag.
EXERCISES

Your exercises.

Part A builds a BST, including the three-case delete; a randomized test runs 2,000 mixed inserts and deletes against a reference set. Part B is the four traversals. Part C is five classic tree problems.

go test ./07-trees/

The test file has a build(...) helper that makes a tree from a level-order list like build(3, 9, 20, X, X, 15, 7) — handy for your own experiments.

The files for this module

Everything below is also in the course download, in 07-trees/. Work in exercises.go; the tests decide when you’re done.

▶ types.go the structs and helpers you’re given · 25 lines› 
// Package trees is Module 7: binary trees and binary search trees.
//
// Most tree code is recursion over a nil-able pointer: handle nil, then
// combine the answers from Left and Right. Get comfortable with that shape
// here — heaps and graphs reuse it.
package trees

// TreeNode is a binary tree node.
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// BST is a binary search tree of distinct ints: for every node, all values
// in Left are smaller and all values in Right are larger.
type BST struct {
	root *TreeNode
	size int
}

// Len returns the number of values stored.
func (t *BST) Len() int { return t.size }

// Root returns the root node (nil when empty).
func (t *BST) Root() *TreeNode { return t.root }
exercises.go — your work: every function is a stub marked TODO113 lines
//go:build !solutions

package trees

// ============================================================
// Part A — binary search tree
// ============================================================

// Insert adds v and returns true, or returns false if v is already present.
// Target: O(h), where h is the tree height.
func (t *BST) Insert(v int) bool {
	// TODO
	return false
}

// Contains reports whether v is in the tree. Target: O(h).
func (t *BST) Contains(v int) bool {
	// TODO
	return false
}

// Min returns the smallest value, or (0, false) if empty. Target: O(h).
func (t *BST) Min() (int, bool) {
	// TODO
	return 0, false
}

// Max returns the largest value, or (0, false) if empty. Target: O(h).
func (t *BST) Max() (int, bool) {
	// TODO
	return 0, false
}

// Delete removes v and reports whether it was present. Three cases:
// leaf (just remove it), one child (splice the child up), two children
// (replace the value with its in-order successor — the min of the right
// subtree — then delete that successor). Target: O(h).
func (t *BST) Delete(v int) bool {
	// TODO
	return false
}

// ============================================================
// Part B — traversals (nil root -> nil result)
// ============================================================

// InOrder visits Left, node, Right. On a BST this yields sorted order.
func InOrder(root *TreeNode) []int {
	// TODO
	return nil
}

// PreOrder visits node, Left, Right. Challenge: do it iteratively with an
// explicit stack instead of recursion.
func PreOrder(root *TreeNode) []int {
	// TODO
	return nil
}

// PostOrder visits Left, Right, node.
func PostOrder(root *TreeNode) []int {
	// TODO
	return nil
}

// LevelOrder returns values level by level, left to right:
// [[3] [9 20] [15 7]]. Pattern: BFS with a queue, one level at a time.
func LevelOrder(root *TreeNode) [][]int {
	// TODO
	return nil
}

// ============================================================
// Part C — tree problems
// ============================================================

// MaxDepth returns the number of nodes on the longest root-to-leaf path
// (0 for nil). Target: O(n).
func MaxDepth(root *TreeNode) int {
	// TODO
	return 0
}

// IsValidBST reports whether the tree satisfies the BST property with
// distinct values. Checking each node only against its children is NOT
// enough — pass down the allowed (lo, hi) range. Target: O(n).
func IsValidBST(root *TreeNode) bool {
	// TODO
	return false
}

// IsBalanced reports whether, at every node, the heights of the two
// subtrees differ by at most 1. Target: O(n) — compute heights bottom-up
// once rather than calling MaxDepth at every node.
func IsBalanced(root *TreeNode) bool {
	// TODO
	return false
}

// Invert mirrors the tree in place (swap Left and Right everywhere) and
// returns the root. Target: O(n).
func Invert(root *TreeNode) *TreeNode {
	// TODO
	return nil
}

// LCA returns the lowest common ancestor of values p and q in a BST (both
// are present). Use the BST ordering: if both are smaller go left, if both
// are larger go right, otherwise you're there. Target: O(h).
func LCA(root *TreeNode, p, q int) *TreeNode {
	// TODO
	return nil
}
▶ trees_test.go the tests — the same file checks yours or the reference · 247 lines› 
package trees

import (
	"math/rand"
	"slices"
	"testing"
)

// X marks a missing child in a level-order description.
const X = -1 << 62

// build creates a tree from a LeetCode-style level-order list.
// build(3, 9, 20, X, X, 15, 7):
//
//	  3
//	 / \
//	9   20
//	   /  \
//	  15   7
func build(vals ...int) *TreeNode {
	if len(vals) == 0 || vals[0] == X {
		return nil
	}
	root := &TreeNode{Val: vals[0]}
	queue := []*TreeNode{root}
	for i := 1; i < len(vals); {
		n := queue[0]
		queue = queue[1:]
		if i < len(vals) && vals[i] != X {
			n.Left = &TreeNode{Val: vals[i]}
			queue = append(queue, n.Left)
		}
		i++
		if i < len(vals) && vals[i] != X {
			n.Right = &TreeNode{Val: vals[i]}
			queue = append(queue, n.Right)
		}
		i++
	}
	return root
}

func TestBSTInsertContains(t *testing.T) {
	var b BST
	for _, v := range []int{50, 30, 70, 20, 40, 60, 80} {
		if !b.Insert(v) {
			t.Fatalf("Insert(%d) = false on a new value", v)
		}
	}
	if b.Insert(40) {
		t.Error("Insert of a duplicate should return false")
	}
	if b.Len() != 7 {
		t.Errorf("Len() = %d, want 7", b.Len())
	}
	for _, v := range []int{20, 50, 80} {
		if !b.Contains(v) {
			t.Errorf("Contains(%d) = false", v)
		}
	}
	for _, v := range []int{0, 45, 99} {
		if b.Contains(v) {
			t.Errorf("Contains(%d) = true", v)
		}
	}
	if mn, ok := b.Min(); !ok || mn != 20 {
		t.Errorf("Min() = (%d, %v), want (20, true)", mn, ok)
	}
	if mx, ok := b.Max(); !ok || mx != 80 {
		t.Errorf("Max() = (%d, %v), want (80, true)", mx, ok)
	}
	var empty BST
	if _, ok := empty.Min(); ok {
		t.Error("Min() on an empty tree should return ok=false")
	}
}

func TestBSTDelete(t *testing.T) {
	var b BST
	for _, v := range []int{50, 30, 70, 20, 40, 60, 80, 65} {
		b.Insert(v)
	}
	steps := []struct {
		del  int
		ok   bool
		want []int
	}{
		{20, true, []int{30, 40, 50, 60, 65, 70, 80}}, // leaf
		{60, true, []int{30, 40, 50, 65, 70, 80}},     // one child
		{50, true, []int{30, 40, 65, 70, 80}},         // two children (root)
		{99, false, []int{30, 40, 65, 70, 80}},        // missing
		{70, true, []int{30, 40, 65, 80}},             // one child again
	}
	for _, s := range steps {
		if ok := b.Delete(s.del); ok != s.ok {
			t.Fatalf("Delete(%d) = %v, want %v", s.del, ok, s.ok)
		}
		if got := InOrder(b.Root()); !slices.Equal(got, s.want) {
			t.Fatalf("after Delete(%d), InOrder = %v, want %v", s.del, got, s.want)
		}
		if !IsValidBST(b.Root()) {
			t.Fatalf("after Delete(%d), tree is no longer a valid BST", s.del)
		}
	}
	if b.Len() != 4 {
		t.Errorf("Len() = %d, want 4", b.Len())
	}
}

func TestBSTRandomized(t *testing.T) {
	r := rand.New(rand.NewSource(7))
	var b BST
	ref := map[int]bool{}
	for i := 0; i < 2000; i++ {
		v := r.Intn(200)
		if r.Intn(3) == 0 {
			if got := b.Delete(v); got != ref[v] {
				t.Fatalf("Delete(%d) = %v, want %v", v, got, ref[v])
			}
			delete(ref, v)
		} else {
			if got := b.Insert(v); got != !ref[v] {
				t.Fatalf("Insert(%d) = %v, want %v", v, got, !ref[v])
			}
			ref[v] = true
		}
	}
	if b.Len() != len(ref) {
		t.Fatalf("Len() = %d, want %d", b.Len(), len(ref))
	}
	var want []int
	for v := range ref {
		want = append(want, v)
	}
	slices.Sort(want)
	if got := InOrder(b.Root()); !slices.Equal(got, want) {
		t.Fatalf("InOrder after random ops differs from reference set")
	}
}

func TestTraversals(t *testing.T) {
	//        1
	//       / \
	//      2   3
	//     / \   \
	//    4   5   6
	root := build(1, 2, 3, 4, 5, X, 6)
	if got, want := InOrder(root), []int{4, 2, 5, 1, 3, 6}; !slices.Equal(got, want) {
		t.Errorf("InOrder = %v, want %v", got, want)
	}
	if got, want := PreOrder(root), []int{1, 2, 4, 5, 3, 6}; !slices.Equal(got, want) {
		t.Errorf("PreOrder = %v, want %v", got, want)
	}
	if got, want := PostOrder(root), []int{4, 5, 2, 6, 3, 1}; !slices.Equal(got, want) {
		t.Errorf("PostOrder = %v, want %v", got, want)
	}
	if InOrder(nil) != nil || PreOrder(nil) != nil || PostOrder(nil) != nil {
		t.Error("traversals of nil should return nil")
	}
}

func TestLevelOrder(t *testing.T) {
	got := LevelOrder(build(3, 9, 20, X, X, 15, 7))
	want := [][]int{{3}, {9, 20}, {15, 7}}
	if !slices.EqualFunc(got, want, slices.Equal[[]int]) {
		t.Errorf("LevelOrder = %v, want %v", got, want)
	}
	if LevelOrder(nil) != nil {
		t.Error("LevelOrder(nil) should be nil")
	}
}

func TestMaxDepth(t *testing.T) {
	for _, tc := range []struct {
		root *TreeNode
		want int
	}{
		{build(3, 9, 20, X, X, 15, 7), 3},
		{build(1, X, 2, X, 3), 3},
		{build(1), 1},
		{nil, 0},
	} {
		if got := MaxDepth(tc.root); got != tc.want {
			t.Errorf("MaxDepth = %d, want %d (tree %v)", got, tc.want, LevelOrder(tc.root))
		}
	}
}

func TestIsValidBST(t *testing.T) {
	for _, tc := range []struct {
		name string
		root *TreeNode
		want bool
	}{
		{"simple", build(2, 1, 3), true},
		{"right child too small", build(5, 1, 4, X, X, 3, 6), false},
		{"grandchild breaks ancestor bound", build(5, 4, 6, X, X, 3, 7), false},
		{"duplicate", build(2, 2, 3), false},
		{"empty", nil, true},
		{"larger", build(8, 4, 12, 2, 6, 10, 14), true},
	} {
		if got := IsValidBST(tc.root); got != tc.want {
			t.Errorf("IsValidBST(%s) = %v, want %v", tc.name, got, tc.want)
		}
	}
}

func TestIsBalanced(t *testing.T) {
	for _, tc := range []struct {
		name string
		root *TreeNode
		want bool
	}{
		{"balanced", build(3, 9, 20, X, X, 15, 7), true},
		{"left-heavy", build(1, 2, 2, 3, 3, X, X, 4, 4), false},
		{"chain", build(1, X, 2, X, 3), false},
		{"root balanced, subtree not", build(1, 2, 3, 4, X, X, 5, 6, X, X, 7), false},
		{"empty", nil, true},
	} {
		if got := IsBalanced(tc.root); got != tc.want {
			t.Errorf("IsBalanced(%s) = %v, want %v", tc.name, got, tc.want)
		}
	}
}

func TestInvert(t *testing.T) {
	got := LevelOrder(Invert(build(4, 2, 7, 1, 3, 6, 9)))
	want := [][]int{{4}, {7, 2}, {9, 6, 3, 1}}
	if !slices.EqualFunc(got, want, slices.Equal[[]int]) {
		t.Errorf("Invert: LevelOrder = %v, want %v", got, want)
	}
	if Invert(nil) != nil {
		t.Error("Invert(nil) should be nil")
	}
}

func TestLCA(t *testing.T) {
	root := build(6, 2, 8, 0, 4, 7, 9, X, X, 3, 5)
	for _, tc := range []struct{ p, q, want int }{
		{2, 8, 6}, {2, 4, 2}, {3, 5, 4}, {0, 5, 2}, {7, 9, 8},
	} {
		got := LCA(root, tc.p, tc.q)
		if got == nil || got.Val != tc.want {
			t.Errorf("LCA(%d, %d) = %v, want node %d", tc.p, tc.q, got, tc.want)
		}
	}
}
Before you open the solution

Try not to open solution.go until your tests pass, or until you’ve been stuck for a solid half hour. Then compare: different-but-correct is fine; notice where the reference is simpler. go test -tags solutions ./07-trees/ runs the same tests against it.

▶ solution.go reference solutions — build tag solutions · 236 lines› 
//go:build solutions

package trees

import "math"

// ---------- BST ----------

func (t *BST) Insert(v int) bool {
	link := &t.root // pointer to the pointer we may need to fill
	for *link != nil {
		switch n := *link; {
		case v < n.Val:
			link = &n.Left
		case v > n.Val:
			link = &n.Right
		default:
			return false
		}
	}
	*link = &TreeNode{Val: v}
	t.size++
	return true
}

func (t *BST) Contains(v int) bool {
	n := t.root
	for n != nil {
		switch {
		case v < n.Val:
			n = n.Left
		case v > n.Val:
			n = n.Right
		default:
			return true
		}
	}
	return false
}

func (t *BST) Min() (int, bool) {
	if t.root == nil {
		return 0, false
	}
	n := t.root
	for n.Left != nil {
		n = n.Left
	}
	return n.Val, true
}

func (t *BST) Max() (int, bool) {
	if t.root == nil {
		return 0, false
	}
	n := t.root
	for n.Right != nil {
		n = n.Right
	}
	return n.Val, true
}

func (t *BST) Delete(v int) bool {
	var deleted bool
	t.root, deleted = deleteNode(t.root, v)
	if deleted {
		t.size--
	}
	return deleted
}

func deleteNode(n *TreeNode, v int) (*TreeNode, bool) {
	if n == nil {
		return nil, false
	}
	var ok bool
	switch {
	case v < n.Val:
		n.Left, ok = deleteNode(n.Left, v)
		return n, ok
	case v > n.Val:
		n.Right, ok = deleteNode(n.Right, v)
		return n, ok
	}
	// Found it.
	if n.Left == nil {
		return n.Right, true
	}
	if n.Right == nil {
		return n.Left, true
	}
	// Two children: copy in the in-order successor, then delete it from the right.
	succ := n.Right
	for succ.Left != nil {
		succ = succ.Left
	}
	n.Val = succ.Val
	n.Right, _ = deleteNode(n.Right, succ.Val)
	return n, true
}

// ---------- Traversals ----------

func InOrder(root *TreeNode) []int {
	var out []int
	var walk func(*TreeNode)
	walk = func(n *TreeNode) {
		if n == nil {
			return
		}
		walk(n.Left)
		out = append(out, n.Val)
		walk(n.Right)
	}
	walk(root)
	return out
}

func PreOrder(root *TreeNode) []int {
	var out []int
	stack := []*TreeNode{}
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		n := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		out = append(out, n.Val)
		if n.Right != nil {
			stack = append(stack, n.Right)
		}
		if n.Left != nil {
			stack = append(stack, n.Left)
		}
	}
	return out
}

func PostOrder(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	out := PostOrder(root.Left)
	out = append(out, PostOrder(root.Right)...)
	return append(out, root.Val)
}

func LevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var out [][]int
	level := []*TreeNode{root}
	for len(level) > 0 {
		var vals []int
		var next []*TreeNode
		for _, n := range level {
			vals = append(vals, n.Val)
			if n.Left != nil {
				next = append(next, n.Left)
			}
			if n.Right != nil {
				next = append(next, n.Right)
			}
		}
		out = append(out, vals)
		level = next
	}
	return out
}

// ---------- Problems ----------

func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + max(MaxDepth(root.Left), MaxDepth(root.Right))
}

func IsValidBST(root *TreeNode) bool {
	var check func(n *TreeNode, lo, hi int) bool
	check = func(n *TreeNode, lo, hi int) bool {
		if n == nil {
			return true
		}
		if n.Val <= lo || n.Val >= hi {
			return false
		}
		return check(n.Left, lo, n.Val) && check(n.Right, n.Val, hi)
	}
	return check(root, math.MinInt, math.MaxInt)
}

func IsBalanced(root *TreeNode) bool {
	// height returns -1 as soon as any subtree is unbalanced.
	var height func(*TreeNode) int
	height = func(n *TreeNode) int {
		if n == nil {
			return 0
		}
		l := height(n.Left)
		if l < 0 {
			return -1
		}
		r := height(n.Right)
		if r < 0 || l-r > 1 || r-l > 1 {
			return -1
		}
		return 1 + max(l, r)
	}
	return height(root) >= 0
}

func Invert(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = Invert(root.Right), Invert(root.Left)
	return root
}

func LCA(root *TreeNode, p, q int) *TreeNode {
	n := root
	for n != nil {
		switch {
		case p < n.Val && q < n.Val:
			n = n.Left
		case p > n.Val && q > n.Val:
			n = n.Right
		default:
			return n
		}
	}
	return nil
}
FURTHER

Going further.

  • Add All() iter.Seq[int] to BST that yields values in order and supports early break.
  • LeetCode practice: Diameter of Binary Tree, Serialize and Deserialize Binary Tree, Kth Smallest Element in a BST.
QUIZ

Check yourself.

Four questions. Answer each one in your head — or out loud — before you open the answer.

Question 1

You insert 1, 2, 3, 4, 5 in that order into an empty, unbalanced BST. What's its height (in nodes)?

  • A3
  • B5
  • C2
  • Dlog₂ 5
Show the answer

B — Each value is larger than everything before it, so each goes right: a chain of 5. Searches degrade to O(n). Self-balancing trees prevent this.

Question 2

Which traversal of a BST yields the values in sorted order?

  • APre-order
  • BIn-order
  • CPost-order
  • DLevel-order
Show the answer

B — Left subtree (all smaller), then the node, then the right subtree (all larger) — recursively, that's sorted.

Question 3

Why isn't checking Left.Val < Val < Right.Val at every node enough for IsValidBST?

  • AIt doesn't handle nil children
  • BA deeper descendant can violate an ancestor's bound — e.g. a 3 in the root 5's right subtree
  • CIt's too slow
  • DIt is enough
Show the answer

B — The BST rule applies to whole subtrees. Pass the allowed (low, high) range down as you recurse.

Question 4

Deleting a BST node with two children: what replaces it?

  • AIts left child
  • BIts in-order successor (the minimum of the right subtree)
  • CThe root
  • DNothing — mark it deleted
Show the answer

B — The successor is larger than everything on the left and smaller than everything else on the right, so the BST property holds. (The in-order predecessor works too.)

NEXT

Where to next.

Commit your work before you move on to module 8, so git log shows your own progress through the course.

6

← Previous: Module 6 — Hashing

Hash tables, collisions, and load factors — then the map-powered patterns that turn O(n²) into O(n).

 8

Next →: Module 8 — Heaps

Always know the smallest (or largest) item. Priority queues, top-k, and container/heap.

 ⌂

Course home

All ten modules, the course download, and how to track your progress.
× Data Structures & Algorithms in Go · module 7 of 10 · trees