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].

Basic Implementation

basic.go 
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)
}

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.
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.