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

using System;
using System.Collections.Generic;

class TreeNode {
	public int Value;
	public int Left;
	public int Right;
}

class Program {
	static int MakeNode(List<TreeNode> nodes, int value, int left, int right) {
		int idx = nodes.Count;
		nodes.Add(new TreeNode { Value = value, Left = left, Right = right });
		return idx;
	}

	static void Inorder(List<TreeNode> nodes, int node, List<int> output) {
		if (node != -1) {
			Inorder(nodes, nodes[node].Left, output);
			output.Add(nodes[node].Value);
			Inorder(nodes, nodes[node].Right, output);
		}
	}

	static void Main() {
		List<TreeNode> nodes = new List<TreeNode>();
		int n1 = MakeNode(nodes, 1, -1, -1);
		int n3 = MakeNode(nodes, 3, -1, -1);
		int n2 = MakeNode(nodes, 2, n1, n3);
		int n5 = MakeNode(nodes, 5, -1, -1);
		int n7 = MakeNode(nodes, 7, -1, -1);
		int n6 = MakeNode(nodes, 6, n5, n7);
		int root = MakeNode(nodes, 4, n2, n6);

		List<int> output = new List<int>();
		Inorder(nodes, root, output);
		Console.WriteLine("[" + string.Join(", ", output) + "]");
	}
}

Complexity

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

Implementation notes

C#: a small class TreeNode { public int Value; public int Left; public int Right; } stored in a List<TreeNode> arena. The arena pattern keeps the recursion focused on traversal without leaning on LinkedList<T> or recursive class references.
The output buffer is a plain List<int> so the Add growth is visible to the caller; the lesson does not lean on a LINQ helper.
The replay shows the running output list and the visited node value on each visit frame, with node(<value>) labels instead of runtime references.

in-order recursion `Inorder(node.left); output.Add(node.value); Inorder(node.right);`.

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