Go Guide

Trees & graphs · Lesson 26 of 62 · about 60 min

Binary trees & BSTs

Recursive thinking on trees: the four traversals, solving problems by combining subtree answers, and binary search trees.

Go by Example: Recursion ↗Go by Example: Range over Iterators ↗
On this page · 11 sections
  1. 01Vocabulary
  2. 02The four traversals
  3. 03Thinking recursively: max depth
  4. 04Level order with a queue
  5. 05Binary search trees
  6. 06Serialize and deserialize a tree
  7. 07The full program
  8. 08Complexity
  9. 09Summary
  10. 10Check your understanding
  11. 11Practice in Go

Vocabulary#

            8          <- root (depth 1)
          /   \
         3     10      <- children of 8
        / \      \
       1   6      14   <- leaves: 1, 6 (if childless), 14
          / \
         4   7
TermMeaning
rootthe top node
leafa node with no children
depth / heightnumber of nodes on the longest root-to-leaf path (4 here: 8, 3, 6, 4)
subtreea node plus all its descendants
balancedleft and right heights differ by at most one everywhere, so height is about log n
Go
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

The four traversals#

TraversalOrderUse it forExample output (tree above)
pre-ordernode, left, rightcopying a tree, serializing8 3 1 6 4 7 10 14
in-orderleft, node, rightBSTs: sorted order1 3 4 6 7 8 10 14
post-orderleft, right, nodecombining children's answers (heights, sums)1 4 7 6 3 14 10 8
level orderrow by row (BFS, with a queue)levels, shortest depth, views8 3 10 1 6 14 4 7

The three depth-first ones differ only in where you handle the node relative to the two recursive calls.

Run it

The tree from the vocabulary section, built by hand, with all three depth-first traversals. Compare each function: the only difference is which line comes first.

traversals.go
Go
package main
 
import "fmt"
 
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
 
func n(v int, l, r *TreeNode) *TreeNode { return &TreeNode{v, l, r} }
 
func preorder(t *TreeNode) {
	if t == nil {
		return
	}
	fmt.Print(t.Val, " ") // node first
	preorder(t.Left)
	preorder(t.Right)
}
 
func inorder(t *TreeNode) {
	if t == nil {
		return
	}
	inorder(t.Left)
	fmt.Print(t.Val, " ") // node in the middle
	inorder(t.Right)
}
 
func postorder(t *TreeNode) {
	if t == nil {
		return
	}
	postorder(t.Left)
	postorder(t.Right)
	fmt.Print(t.Val, " ") // node last
}
 
func main() {
	root := n(8,
		n(3, n(1, nil, nil), n(6, n(4, nil, nil), n(7, nil, nil))),
		n(10, nil, n(14, nil, nil)))
	fmt.Print("pre:  ")
	preorder(root)
	fmt.Print("\nin:   ")
	inorder(root)
	fmt.Print("\npost: ")
	postorder(root)
	fmt.Println()
}
Output
pre:  8 3 1 6 4 7 10 14 
in:   1 3 4 6 7 8 10 14 
post: 1 4 7 6 3 14 10 8

Thinking recursively: max depth#

Do not try to picture the whole recursion. Trust it:

  1. Base case: an empty tree (nil) has depth 0.
  2. Assume the recursive calls return correct depths for the left and right subtrees.
  3. Combine: the depth here is 1 + max(left, right).

Trace on the small tree 3 → (1, 6 → (4, nil)):

callleft returnsright returnsreturns
depth(1)001
depth(4)001
depth(6)1 (node 4)02
depth(3)1 (node 1)2 (node 6)3

Run the trace

Each call prints when it starts, indented by depth, and what it returns once both children have answered. The returns arrive bottom-up: post-order.

depth_trace.go
Go
package main
 
import (
	"fmt"
	"strings"
)
 
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
 
func depth(t *TreeNode, level int) int {
	if t == nil {
		return 0
	}
	pad := strings.Repeat("  ", level)
	fmt.Printf("%sdepth(%d)\n", pad, t.Val)
	l := depth(t.Left, level+1)
	r := depth(t.Right, level+1)
	fmt.Printf("%sdepth(%d): left %d, right %d -> %d\n", pad, t.Val, l, r, 1+max(l, r))
	return 1 + max(l, r)
}
 
func main() {
	root := &TreeNode{3, &TreeNode{Val: 1}, &TreeNode{6, &TreeNode{Val: 4}, nil}}
	fmt.Println("answer:", depth(root, 0))
}
Output
depth(3)
  depth(1)
  depth(1): left 0, right 0 -> 1
  depth(6)
    depth(4)
    depth(4): left 0, right 0 -> 1
  depth(6): left 1, right 0 -> 2
depth(3): left 1, right 2 -> 3
answer: 3

Level order with a queue#

Put the root in a queue. While the queue is not empty, take all nodes currently in it (that is exactly one level), record their values, and queue their children for the next level.

Run the trace

levels_trace.go
Go
package main
 
import "fmt"
 
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
 
func n(v int, l, r *TreeNode) *TreeNode { return &TreeNode{v, l, r} }
 
func main() {
	root := n(8,
		n(3, n(1, nil, nil), n(6, n(4, nil, nil), n(7, nil, nil))),
		n(10, nil, n(14, nil, nil)))
 
	queue := []*TreeNode{root}
	for level := 1; len(queue) > 0; level++ {
		size := len(queue) // exactly the nodes on this level
		var vals []int
		for range size {
			node := queue[0]
			queue = queue[1:]
			vals = append(vals, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		fmt.Printf("level %d: %v  queued for next: %d\n", level, vals, len(queue))
	}
}
Output
level 1: [8]  queued for next: 2
level 2: [3 10]  queued for next: 3
level 3: [1 6 14]  queued for next: 2
level 4: [4 7]  queued for next: 0

Binary search trees#

A BST keeps this rule at every node: everything in the left subtree is smaller, everything in the right subtree is larger. Searching is like binary search: compare with the node and go left or right, discarding a whole subtree each step. That is O(height), which is O(log n) when balanced and O(n) when the tree degenerates into a line (inserting sorted data into a plain BST does this).

Validating a BST needs bounds: when you go left from a node with value v, everything below must be < v; going right, > v. Pass (lo, hi) down the recursion and narrow it at each step.

Go's standard library has no balanced tree type. In practice you use a sorted slice with binary search, a map, or a third-party B-tree. Tree problems are still essential for interviews and for understanding indexes, file systems and parsers.

Run the trace: insert and search

Every insert and search prints the path it takes. Notice that each comparison discards a whole subtree. At the end, the same values inserted in sorted order produce a "tree" that is really a line, which is the O(n) worst case:

bst_trace.go
Go
package main
 
import "fmt"
 
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
 
func insert(t *TreeNode, v int) *TreeNode {
	if t == nil {
		return &TreeNode{Val: v}
	}
	if v < t.Val {
		t.Left = insert(t.Left, v)
	} else {
		t.Right = insert(t.Right, v)
	}
	return t
}
 
func search(t *TreeNode, v int) bool {
	fmt.Printf("search %d:", v)
	for t != nil {
		fmt.Printf(" %d", t.Val)
		switch {
		case v == t.Val:
			fmt.Println(" found")
			return true
		case v < t.Val:
			fmt.Print(" ->left")
			t = t.Left
		default:
			fmt.Print(" ->right")
			t = t.Right
		}
	}
	fmt.Println(" nil: missing")
	return false
}
 
func height(t *TreeNode) int {
	if t == nil {
		return 0
	}
	return 1 + max(height(t.Left), height(t.Right))
}
 
func main() {
	var root *TreeNode
	for _, v := range []int{8, 3, 10, 1, 6, 14, 4, 7} {
		root = insert(root, v)
	}
	search(root, 7)
	search(root, 5)
	fmt.Println("height:", height(root))
 
	var line *TreeNode
	for _, v := range []int{1, 3, 4, 6, 7, 8, 10, 14} { // sorted input
		line = insert(line, v)
	}
	fmt.Println("height after sorted inserts:", height(line))
}
Output
search 7: 8 ->left 3 ->right 6 ->right 7 found
search 5: 8 ->left 3 ->right 6 ->left 4 ->right nil: missing
height: 4
height after sorted inserts: 8

Step through it

Insert 1 2 3 4 5 6 to see a sorted input build a degenerate, list-shaped tree.

Serialize and deserialize a tree#

To save a tree to a file, send it over a network, or cache it in Redis, you need to turn it into a string and back. The key insight: a pre-order traversal with explicit markers for nil children describes a tree uniquely. Without the markers, 1 2 could be "2 is the left child" or "2 is the right child".

    1          pre-order with nils:  1 2 # # 3 4 # # 5 # #
   / \
  2   3        decode: read 1, then decode its left subtree (2 # #),
     / \       then its right subtree (3 4 # # 5 # #)
    4   5

Decoding reads tokens in the same order: each call consumes a value and then recursively builds the left and right subtrees, or consumes a # and returns nil.

serialize.go
Go
package main
 
import (
	"fmt"
	"strconv"
	"strings"
)
 
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
 
func Serialize(root *TreeNode) string {
	var b strings.Builder
	var walk func(n *TreeNode)
	walk = func(n *TreeNode) {
		if n == nil {
			b.WriteString("# ")
			return
		}
		b.WriteString(strconv.Itoa(n.Val))
		b.WriteByte(' ')
		walk(n.Left)
		walk(n.Right)
	}
	walk(root)
	return strings.TrimSpace(b.String())
}
 
func Deserialize(data string) (*TreeNode, error) {
	tokens := strings.Fields(data)
	i := 0
	var build func() (*TreeNode, error)
	build = func() (*TreeNode, error) {
		if i >= len(tokens) {
			return nil, fmt.Errorf("unexpected end of input")
		}
		tok := tokens[i]
		i++
		if tok == "#" {
			return nil, nil
		}
		v, err := strconv.Atoi(tok)
		if err != nil {
			return nil, fmt.Errorf("token %d: %w", i, err)
		}
		n := &TreeNode{Val: v}
		if n.Left, err = build(); err != nil {
			return nil, err
		}
		if n.Right, err = build(); err != nil {
			return nil, err
		}
		return n, nil
	}
	root, err := build()
	if err == nil && i != len(tokens) {
		err = fmt.Errorf("%d extra tokens", len(tokens)-i)
	}
	return root, err
}
 
func main() {
	t := &TreeNode{1, &TreeNode{Val: 2}, &TreeNode{3, &TreeNode{Val: 4}, &TreeNode{Val: 5}}}
	s := Serialize(t)
	fmt.Printf("%q\n", s)
 
	back, err := Deserialize(s)
	fmt.Println(err, Serialize(back) == s, back.Right.Left.Val)
 
	_, err = Deserialize("1 2 #")
	fmt.Println("broken input:", err)
	_, err = Deserialize("1 x # #")
	fmt.Println("bad number:", err)
}
Output
"1 2 # # 3 4 # # 5 # #"
<nil> true 4
broken input: unexpected end of input
bad number: token 2: strconv.Atoi: parsing "x": invalid syntax

Treat the input of Deserialize as untrusted: it returns errors instead of panicking on truncated or malformed data, which matters as soon as the string comes from a file or a network. Production systems often use JSON or Protocol Buffers instead, but the idea of encoding structure explicitly is the same. A level-order (BFS) encoding with # markers, the format LeetCode uses, works just as well.

The full program#

trees.go
Go
package main
 
import (
	"fmt"
	"iter"
	"math"
)
 
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}
 
func insert(root *TreeNode, v int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: v}
	}
	if v < root.Val {
		root.Left = insert(root.Left, v)
	} else {
		root.Right = insert(root.Right, v)
	}
	return root
}
 
func preorder(n *TreeNode, out *[]int) {
	if n == nil {
		return
	}
	*out = append(*out, n.Val)
	preorder(n.Left, out)
	preorder(n.Right, out)
}
 
// InOrder is a Go 1.23 iterator: for v := range InOrder(root) { ... }
func InOrder(root *TreeNode) iter.Seq[int] {
	return func(yield func(int) bool) {
		var walk func(n *TreeNode) bool
		walk = func(n *TreeNode) bool {
			if n == nil {
				return true
			}
			return walk(n.Left) && yield(n.Val) && walk(n.Right)
		}
		walk(root)
	}
}
 
func maxDepth(n *TreeNode) int {
	if n == nil {
		return 0
	}
	return 1 + max(maxDepth(n.Left), maxDepth(n.Right))
}
 
func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	var q []*TreeNode
	if root != nil {
		q = append(q, root)
	}
	for len(q) > 0 {
		level := make([]int, 0, len(q))
		var next []*TreeNode
		for _, n := range q {
			level = append(level, n.Val)
			if n.Left != nil {
				next = append(next, n.Left)
			}
			if n.Right != nil {
				next = append(next, n.Right)
			}
		}
		res = append(res, level)
		q = next
	}
	return res
}
 
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 search(n *TreeNode, v int) bool {
	for n != nil {
		switch {
		case v < n.Val:
			n = n.Left
		case v > n.Val:
			n = n.Right
		default:
			return true
		}
	}
	return false
}
 
func invert(n *TreeNode) *TreeNode {
	if n != nil {
		n.Left, n.Right = invert(n.Right), invert(n.Left)
	}
	return n
}
 
func main() {
	var root *TreeNode
	for _, v := range []int{8, 3, 10, 1, 6, 14, 4, 7} {
		root = insert(root, v)
	}
 
	var pre []int
	preorder(root, &pre)
	fmt.Println("pre:  ", pre)
 
	fmt.Print("in:    ")
	for v := range InOrder(root) {
		fmt.Print(v, " ")
	}
	fmt.Println()
 
	fmt.Println("levels:", levelOrder(root))
	fmt.Println("depth:", maxDepth(root), "valid BST:", isValidBST(root))
	fmt.Println("has 6:", search(root, 6), "has 5:", search(root, 5))
 
	for v := range InOrder(root) {
		if v > 4 {
			fmt.Println("first value over 4:", v) // stops the walk early
			break
		}
	}
 
	invert(root)
	fmt.Println("after invert, valid BST:", isValidBST(root), levelOrder(root)[1])
}
Output
pre:   [8 3 1 6 4 7 10 14]
in:    1 3 4 6 7 8 10 14 
levels: [[8] [3 10] [1 6 14] [4 7]]
depth: 4 valid BST: true
has 6: true has 5: false
first value over 4: 6
after invert, valid BST: false [10 3]

The iterator's walk returns false as soon as yield does, so break in the caller's loop stops the traversal immediately instead of visiting the rest of the tree.

Complexity#

OperationTimeSpace
any traversalO(n)O(h) recursion (h = height), O(width) for BFS
max depth, invert, validateO(n)O(h)
BST search / insertO(h): O(log n) balanced, O(n) worstO(1) iterative

Summary#

  • Trees are recursive: base case nil, trust the calls on subtrees, combine at the node.
  • Pre-, in- and post-order differ in when you handle the node; level order uses a queue.
  • BST rule: left smaller, right larger, for whole subtrees; operations cost O(height).
  • Validate BSTs by passing bounds down; in-order traversal of a BST is sorted.
  • Go 1.23 iterators make custom traversals work with for range, including early break.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.In-order traversal of a valid BST produces values in:

  2. Q2.Which traversal uses a queue?

  3. Q3.Why is checking left.Val < node.Val < right.Val at each node not enough to validate a BST?

  4. Q4.Searching a balanced BST with n nodes takes:

  5. Q5.Max depth = 1 + max(depth(left), depth(right)) is an example of:

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.