Lesson 5 of 8Article22 min
Trees and Tree Traversals
Trees and Tree Traversals
Tree fundamentals
- Binary tree node has up to two children.
- Binary Search Tree (BST): left < node < right.
- Depth-first traversals: preorder, inorder, postorder.
- Breadth-first traversal uses a queue.
Recursive DFS traversal
Inorder traversal
type TreeNode = { value: number; left: TreeNode | null; right: TreeNode | null };
function inorder(root: TreeNode | null, out: number[] = []): number[] {
if (!root) return out;
inorder(root.left, out);
out.push(root.value);
inorder(root.right, out);
return out;
}