Core Data Structures

Trees & Traversals

A tree is a connected, acyclic graph with a designated root — the hierarchical shape behind file systems, expression parsing, and every balanced search structure. Traversal order (preorder, inorder, postorder, level-order) determines what question the walk answers.

A binary tree node has at most two children; general trees allow any number
Preorder (root, left, right): reconstruct the tree structure, serialize it, or clone it
Inorder (left, root, right): visits a binary search tree in sorted order — see Binary Search Trees
Postorder (left, right, root): process children before the parent — deleting a tree, computing subtree sizes
Level-order (breadth-first, one level at a time) needs a queue, not the call stack — see Graph Traversal Bfs Dfs
Height h of a balanced binary tree with n nodes is Θ(log n); a degenerate (linked-list-shaped) tree has height Θ(n)

The three depth-first traversal orders on the same tree
Order	Visit sequence	Typical use
Preorder	root → left → right	Copy/serialize a tree; prefix expression
Inorder	left → root → right	Sorted output of a BST
Postorder	left → right → root	Delete a tree; evaluate an expression tree

The three recursive traversals, side by side

record TreeNode(int val, TreeNode left, TreeNode right) {}

static void preorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    out.add(n.val());              // visit root first
    preorder(n.left(), out);
    preorder(n.right(), out);
}

static void inorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    inorder(n.left(), out);
    out.add(n.val());              // visit root between children
    inorder(n.right(), out);
}

static void postorder(TreeNode n, List<Integer> out) {
    if (n == null) return;
    postorder(n.left(), out);
    postorder(n.right(), out);
    out.add(n.val());              // visit root last
}

Level-order traversal needs a queue, not recursion

static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<>();
    if (root == null) return levels;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>(levelSize);
        for (int i = 0; i < levelSize; i++) {
            TreeNode n = queue.poll();
            level.add(n.val());
            if (n.left() != null) queue.add(n.left());
            if (n.right() != null) queue.add(n.right());
        }
        levels.add(level);
    }
    return levels;
}