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.cpp 
#include <iostream>
#include <vector>

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v, TreeNode* l, TreeNode* r) : value(v), left(l), right(r) {}
};

void inorder(TreeNode* node, std::vector<int>& out) {
    if (node == nullptr) {
        return;
    }
    inorder(node->left, out);
    out.push_back(node->value);
    inorder(node->right, out);
}

int main() {
    TreeNode* n1 = new TreeNode(1, nullptr, nullptr);
    TreeNode* n3 = new TreeNode(3, nullptr, nullptr);
    TreeNode* n2 = new TreeNode(2, n1, n3);
    TreeNode* n5 = new TreeNode(5, nullptr, nullptr);
    TreeNode* n7 = new TreeNode(7, nullptr, nullptr);
    TreeNode* n6 = new TreeNode(6, n5, n7);
    TreeNode* root = new TreeNode(4, n2, n6);

    std::vector<int> output;
    inorder(root, output);
    std::cout << "[";
    for (size_t i = 0; i < output.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << output[i];
    }
    std::cout << "]" << std::endl;
    return 0;
}

Complexity

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

Implementation notes

  • C++: a small struct TreeNode holds int value, TreeNode* left, and TreeNode* right. The recursion is the smallest possible reusable shape; nullptr is the explicit empty-subtree sentinel.
  • The replay shows the running output vector and the visited node value on each visit frame, with node(<value>) labels instead of raw pointer addresses.
in-order recursion `inorder(node->left); output.push_back(node->value); inorder(node->right);`
BST invariant The same recursion on a binary search tree always emits values in ascending order.