Trees

In-Order Traversal (BST)

Recurse left, visit(node), recurse right. On a binary search tree, this emits values in ascending order — a useful invariant to teach.

Algorithm

Canonical tree 4(2(1, 3), 6(5, 7)) is a balanced BST. In-order traversal yields [1, 2, 3, 4, 5, 6, 7].

in-order recursion `inorder(node.Left, out); *out = append(*out, node.Value); inorder(node.Right, out)`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.

Basic Implementation

basic.go
Replay: real traced execution (multi-file project)
package main

import "fmt"

type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}

func makeTree(v int, l, r *TreeNode) *TreeNode {
	return &TreeNode{Value: v, Left: l, Right: r}
}

func inorder(node *TreeNode, out *[]int) {
	if node == nil {
		return
	}
	inorder(node.Left, out)
	*out = append(*out, node.Value)
	inorder(node.Right, out)
}

func main() {
	n1 := makeTree(1, nil, nil)
	n3 := makeTree(3, nil, nil)
	n2 := makeTree(2, n1, n3)
	n5 := makeTree(5, nil, nil)
	n7 := makeTree(7, nil, nil)
	n6 := makeTree(6, n5, n7)
	root := makeTree(4, n2, n6)

	output := []int{}
	inorder(root, &output)
	fmt.Println(output)
}

  1. output ← [], tree ← 4(2(1,3),6(5,7))

    33output := []int{}34inorder(root, &output)
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    19inorder(node.Left, out)20*out = append(*out, node.Value)21inorder(node.Right, out)
    values this step[] → [1]output

  3. output ← [1, 2]

    19inorder(node.Left, out)20*out = append(*out, node.Value)21inorder(node.Right, out)
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    19inorder(node.Left, out)20*out = append(*out, node.Value)21inorder(node.Right, out)
    values this step[1, 2] → [1, 2, 3]output

  5. output ← [1, 2, 3, 4]

    19inorder(node.Left, out)20*out = append(*out, node.Value)21inorder(node.Right, out)
    values this step[1, 2, 3] → [1, 2, 3, 4]output

  6. output ← [1, 2, 3, 4, 5]

    19inorder(node.Left, out)20*out = append(*out, node.Value)21inorder(node.Right, out)
    values this step[1, 2, 3, 4] → [1, 2, 3, 4, 5]output

  7. output ← [1, 2, 3, 4, 5, 6]

    19inorder(node.Left, out)20*out = append(*out, node.Value)21inorder(node.Right, out)
    values this step[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]output

  8. output ← [1, 2, 3, 4, 5, 6, 7]

    19inorder(node.Left, out)20*out = append(*out, node.Value)21inorder(node.Right, out)
    values this step[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]output

  9. stdout ← [1 2 3 4 5 6 7]

    34	inorder(root, &output)35	fmt.Println(output)36}
    values this step[1 2 3 4 5 6 7]stdout[1, 2, 3, 4, 5, 6, 7]output

Complexity

  • Time: O(n)
  • Space: O(h) call stack

Implementation notes

  • Go: a small type TreeNode struct { Value int; Left, Right *TreeNode } holds the node. The recursion is the smallest possible reusable shape; nil is the explicit empty-subtree sentinel.
  • The output buffer is a plain []int passed by pointer so append growth is visible to the caller; the lesson does not lean on a package container.
  • The replay shows the running output slice and the visited node value on each visit frame, with node(<value>) labels instead of raw pointer addresses.