Trees & Binary Trees

From a line to a hierarchy

A tree starts at a single node called the root, the top of a family tree. Each node can point to child nodes below it, and every node except the root has exactly one parent. Nodes with no children are called leaves. A tree never loops back on itself: you can never follow child links and end up where you started.

A binary tree is the most common flavor in interviews: each node has at most two children, called left and right. In Java, a node is just a tiny class holding a value and two references. If a child is missing, its reference is null. That is the whole structure, a binary tree is nothing more than nodes pointing at nodes, with null marking every dead end.

Two words you will hear constantly: the depth of a node is how many steps it is from the root, and the height of the tree is the depth of its deepest node. A tree holding n nodes can be as short as about log n levels (nicely balanced) or as tall as n levels (a straight chain), and that difference drives the performance of everything built on trees.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

The four ways to walk a tree

Traversing a tree means visiting every node exactly once, and the order you choose changes what the walk is good for. Three of the four orders are depth-first: they dive down one branch before backing up. The names tell you when the current node is handled relative to its children.

Pre-order visits the node first, then its left subtree, then its right subtree. Root, left, right. It is the order you would use to copy a tree, because you create a parent before its children. In-order visits left subtree, then the node, then the right subtree. Left, root, right. Post-order visits both subtrees before the node. Left, right, root. It is the order for deleting a tree, because you remove children before their parent, and for any problem where a node's answer depends on its children's answers.

The fourth order, level-order, is breadth-first: visit the root, then every node at depth 1, then every node at depth 2, and so on. Reading the tree line by line like a book. You implement it with a queue rather than recursion, and it is the go-to whenever a problem says level, layer, or shortest path in a tree.

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    System.out.println(node.val);
    inorder(node.right);
}

Recursion is the natural language of trees

Notice how short that in-order method is. That is no accident: a tree is a recursive structure (every node is itself the root of a smaller tree) so recursive code fits it perfectly. Almost every tree solution follows the same template. First, a base case: if the node is null, return a trivial answer. Then, recursive calls on node.left and node.right. Finally, combine those two results with the current node's value.

The mental trick is to trust the recursion. When computing the height of a tree, do not try to trace every call in your head. Just assume height(node.left) and height(node.right) already return the correct heights of the subtrees (the base case guarantees the chain bottoms out) and ask: given those two answers, what is my answer? It is one plus the larger of the two. That single leap of faith turns intimidating tree problems into three-line solutions.

Every depth-first traversal touches each node once, so these run in O(n) time, where n is the number of nodes. The recursion uses the call stack, so space is O(h), where h is the tree's height.

int height(TreeNode node) {
    if (node == null) return 0;
    int left = height(node.left);
    int right = height(node.right);
    return 1 + Math.max(left, right);
}

Level-order with a queue

Level-order traversal swaps recursion for a queue, a first-in, first-out line, like people waiting at a counter. Start by adding the root. Then repeat: remove the node at the front, visit it, and add its children to the back. Because children always join behind everything already waiting, depth 1 nodes are all processed before any depth 2 node, and the tree comes out level by level.

A common interview twist is to group the output by level. Before draining each level, record the queue's current size (that is exactly how many nodes belong to this level) and process only that many before starting the next batch.

So far our trees have no rules about where values live, which means finding a value still requires checking every node. Next up is the binary search tree, which adds one ordering rule and turns that O(n) hunt into an O(log n) descent.

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

Frequently asked