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

import java.util.ArrayList;
import java.util.List;

public class Basic {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode(int value, TreeNode left, TreeNode right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static final List<Integer> output = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1, null, null);
        TreeNode n3 = new TreeNode(3, null, null);
        TreeNode n2 = new TreeNode(2, n1, n3);
        TreeNode n5 = new TreeNode(5, null, null);
        TreeNode n7 = new TreeNode(7, null, null);
        TreeNode n6 = new TreeNode(6, n5, n7);
        TreeNode root = new TreeNode(4, n2, n6);
        inorder(root);
        System.out.println(output);
    }

    private static void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        output.add(node.value);
        inorder(node.right);
    }
}

Complexity

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

Implementation notes

Java: a small static inner class TreeNode holds value, left, and right. The recursion is the smallest possible reusable shape.
The replay shows the running output list and the visited node value on each visit frame.

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.