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

struct TreeNode {
	value: i32,
	left: Option<usize>,
	right: Option<usize>,
}

fn make_node(nodes: &mut Vec<TreeNode>, value: i32, left: Option<usize>, right: Option<usize>) -> usize {
	let idx = nodes.len();
	nodes.push(TreeNode { value, left, right });
	idx
}

fn inorder(nodes: &Vec<TreeNode>, node: Option<usize>, out: &mut Vec<i32>) {
	if let Some(idx) = node {
		inorder(nodes, nodes[idx].left, out);
		out.push(nodes[idx].value);
		inorder(nodes, nodes[idx].right, out);
	}
}

fn main() {
	let mut nodes: Vec<TreeNode> = Vec::new();
	let n1 = make_node(&mut nodes, 1, None, None);
	let n3 = make_node(&mut nodes, 3, None, None);
	let n2 = make_node(&mut nodes, 2, Some(n1), Some(n3));
	let n5 = make_node(&mut nodes, 5, None, None);
	let n7 = make_node(&mut nodes, 7, None, None);
	let n6 = make_node(&mut nodes, 6, Some(n5), Some(n7));
	let root = make_node(&mut nodes, 4, Some(n2), Some(n6));

	let mut output: Vec<i32> = Vec::new();
	inorder(&nodes, Some(root), &mut output);
	println!("{:?}", output);
}

Complexity

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

Implementation notes

Rust: a small struct TreeNode { value: i32, left: Option<usize>, right: Option<usize> } stored in a Vec<TreeNode> arena. The arena pattern keeps the recursion focused on traversal without unsafe pointer juggling or Rc<RefCell<...>> borrowing.
The output buffer is a plain Vec<i32> passed as &mut so the push growth is visible to the caller; the lesson does not lean on a package container.
The replay shows the running output vector and the visited node value on each visit frame, with node(<value>) labels instead of raw addresses.

in-order recursion `inorder(node.left); out.push(node.value); inorder(node.right);`.

BST invariant The same recursion on a binary search tree always emits values in ascending order.