Inorder traversal

Left subtree, then the node, then the right subtree. On a BST this yields the keys in sorted order.

Time O(n)Space O(h)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Recursion does the bookkeeping. Each call finishes everything on its left before recording itself, and only then explores the right.

Code

C++PythonC#

void inorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    inorder(node->left, result);
    result.push_back(node->val);
    inorder(node->right, result);
}

def inorder(node: TreeNode | None, result: list[int]) -> None:
    if node is None: return
    inorder(node.left, result)
    result.append(node.val)
    inorder(node.right, result)

public static void Inorder(TreeNode node, List<int> result) {
    if (node == null) return;
    Inorder(node.left, result);
    result.Add(node.val);
    Inorder(node.right, result);
}

Tips

Use it to read a BST in sorted order, or to check that a tree is a valid BST.

In the .NET library

foreach over a SortedSet<T> is an inorder walk of its red-black tree, which is why it yields items in order.