Tree Algorithms
Binary Tree Inorder Traversal
Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.
1Detailed explanation
Inorder traversal visits a binary tree in the order Left subtree → Node → Right subtree. The recursive definition is short, but the call stack does a lot of work: every call waits for its left child's call to finish before visiting its own node.
On a Binary Search Tree, inorder traversal returns the values in ascending order — a fact used to validate BSTs and to find the k-th smallest element.
Recursion depth equals the tree height h, so extra space is O(h): O(log n) for balanced trees but O(n) for a skewed tree.
2Pseudocode
procedure inorder(node, result)
if node = null
return
inorder(node.left, result)
result.append(node.value)
inorder(node.right, result)3Interactive visualization
Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function inorder(node, result) {
if (node === null) {
return;
}
inorder(node.left, result);
result.push(node.value);
inorder(node.right, result);
}
function buildTree(values) {
if (values.length === 0 || values[0] === null) return null;
const root = new TreeNode(values[0]);
const queue = [root];
let i = 1;
while (queue.length > 0 && i < values.length) {
const node = queue.shift();
if (i < values.length && values[i] !== null) {
node.left = new TreeNode(values[i]);
queue.push(node.left);
}
i++;
if (i < values.length && values[i] !== null) {
node.right = new TreeNode(values[i]);
queue.push(node.right);
}
i++;
}
return root;
}
const root = buildTree([4, 2, 6, 1, 3, 5, 7]);
const result = [];
inorder(root, result);
console.log("Inorder:", result);
5Time and space complexity
Time: Every node is visited exactly once and each call does O(1) work besides its recursive calls. There are n node calls plus n+1 calls on empty (null) children → O(n).
Space: The recursion stack holds one frame per level on the current path, so auxiliary space is O(h) where h is the tree height: O(log n) for a balanced tree, O(n) for a skewed (linked-list-like) tree. The result list adds O(n).
6Common interview variations
- Iterative inorder with an explicit stack.
- Morris traversal in O(1) extra space.
- Validate a Binary Search Tree.
- k-th smallest element in a BST.
- Preorder and postorder traversals.