Binary Trees Explained: Traversals, Height, and Why In-Order Is Sorted

Two teams walk onto the field. Ninety minutes later one of them walks off, and a little line on the tournament bracket carries their name one rung higher — toward the trophy at the very top. You’ve filled one of these in for an office match, a fantasy league, a school quiz. And you already know how to read it: to find the eventual champion, you find each half’s winner first, then let those two fight it out.

That bracket is a binary tree, the shape that quietly underlies sorted data, fast search, file systems, expression parsers, and the index inside every database. It’s the most important structure you’ll learn, because a dozen others are just binary trees wearing a costume. By the end of this article you and I will have built one together — traversals, height, and the one rule that makes it searchable — and you’ll see exactly why an in-order walk comes out sorted.

Let’s start nowhere near a computer

Stay with the bracket for a minute, because it carries the whole idea.

Look at what a knockout bracket is made of. Every match has exactly two feeders below it — the two teams (or two earlier winners) that play into it. Never three, never five. That "up to two" is the entire premise of a binary tree: each spot has a left child and a right child, and that’s the ceiling.

Now read the vocabulary straight off the picture:

• The trophy at the top is the root — the one node everything hangs from.
• The teams at the bottom are the leaves — nodes with nobody below them.
• The rounds are the tree’s height — how many matches deep it goes.

And here’s the part that matters most. You cannot decide the final until both semifinals are done. To know the champion, you first need the left half’s winner and the right half’s winner — and each of those needed their two feeders first. The question "who wins this bracket?" is answered by asking the same question about two smaller brackets. That self-similarity — a tree is a node with a left subtree and a right subtree, each of which is itself a tree — is why almost every operation on a binary tree is a three-line recursive function. The structure recurses, so the code recurses.

The same shape, all over your day

Once you see "a value with up to two children," you spot it everywhere. Your file explorer’s folders nest into folders. A calculator turns 3 + 4 * 5 into an expression tree where * sits below +, so multiplication resolves first. The autocomplete you met in the trie is a tree keyed by letters. The priority queue that powers Dijkstra’s algorithm is a binary heap — a binary tree kept in an array.

But the most useful cousin is the one hiding inside your database. When you look up a user by id in a table of fifty million rows, the database does not scan fifty million rows. It walks an index — a tree — halving the search space at every step, so it reaches your row in a couple of dozen hops instead of fifty million.

That "halve it every step" is the binary-tree superpower, and it’s worth pinning down precisely, because it’s also the one thing that can go wrong. A tree that splits evenly turns n items into about log₂ n steps: a million rows in ~20 hops, a billion in ~30. But the same nodes arranged badly — a tree that leans all the way to one side — degrades into a plain list, and those 30 hops become a billion. Real databases don’t use a bare binary tree for exactly this reason; they use a B-tree, a bushy, self-balancing relative that guarantees the shape stays short. Same descend-by-halving idea, with a hard promise about height bolted on — and that promise is the deep end of this article.

What a binary tree actually looks like

Let’s fix one tree and use it for the rest of the article. Five friendly little values, arranged like this:

Read the names off it once more, now with the precise definitions:

• Root — the topmost node (4 here). It has no parent.
• Leaf — a node with no children (1, 3, 5, 7).
• Internal node — anything that isn’t a leaf (2, 6, and the root).
• Depth of a node — how many edges lie between it and the root. The root is depth 0; 5 is depth 2.
• Height of the tree — the depth of its deepest leaf; the length of the longest root-to-leaf path. This tree’s height is 2.

Let’s build one, step by step

Time to turn the picture into code. Small pieces first; the whole class at the end.

Step 1: the node

Every box in the diagram is one node, and a node needs exactly three things: a value, a link to its left child, and a link to its right child. A missing child is simply null — an empty slot.

public static final class Node {
    final int value;
    Node left;
    Node right;
 
    public Node(int value) {
        this.value = value;
    }
 
    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

Notice what a node does not have: any rule about which child is bigger. A plain binary tree is just shape. The moment we add "left is smaller, right is bigger" it becomes a search tree — but that promise comes later. For now, left and right are just two directions.

Step 2: recursion mirrors the tree

Before any traversal, internalize the pattern, because it’s the same skeleton every single time:

private void walk(Node node) {
    if (node == null) {
        return;              // an empty tree — nothing to do
    }
    // ... do something with node.value ...
    walk(node.left);         // recurse into the left subtree
    walk(node.right);        // recurse into the right subtree
}

That’s it. The null check is the base case — the bottom of every branch. The two recursive calls mirror the two subtrees. The only decision left is when you do something with node.value — before the recursions, between them, or after. That single choice is the whole difference between the three traversals we’re about to write.

Step 3: the three depth-first orders

A depth-first traversal plunges to the bottom of one branch before backing up to try the next — like tracing the bracket down to the teams before moving across. There are three of them, and they differ only in where the "visit" line sits.

Say you want the values sorted. Your first instinct might be to visit the node first, then its children — pre-order:

private void preorder(Node node, List<Integer> out) {
    if (node == null) {
        return;
    }
    out.add(node.value);       // visit BEFORE the children
    preorder(node.left, out);
    preorder(node.right, out);
}

Run it on our tree and you get 4 2 1 3 6 5 7 — the root barges in first, then the whole left half, then the right. Useful for copying a tree or printing a nested outline, but nowhere near sorted.

Now move the visit line down by one, so you emit the node between the two recursions — in-order:

private void inorder(Node node, List<Integer> out) {
    if (node == null) {
        return;
    }
    inorder(node.left, out);
    out.add(node.value);       // visit BETWEEN the children
    inorder(node.right, out);
}

Same tree, and now it prints 1 2 3 4 5 6 7 — perfectly sorted. One line moved, and the output flipped from scrambled to ordered. Why that happens is the deep dive below; for now, savour that the visit’s position is the entire mechanism.

The third position — visit last, after both children — is post-order:

private void postorder(Node node, List<Integer> out) {
    if (node == null) {
        return;
    }
    postorder(node.left, out);
    postorder(node.right, out);
    out.add(node.value);       // visit AFTER both children
}

That yields 1 3 2 5 7 6 4 — children always before their parent. This is the bracket’s real running order: you can’t record the final’s winner until both semifinal winners exist. Post-order is how you evaluate an expression tree, compute folder sizes, or free a tree bottom-up.

Step 4: level-order needs a queue

Depth-first goes down. But sometimes you want to read the tree across — the whole top row, then the next row, then the next. That’s level-order, also called breadth-first search (BFS), and it’s the natural way to print a bracket round by round.

Here’s the trap. Recursion — and its cousin, an explicit stack — is a depth-first tool: it sends you plunging down one branch before you’ve finished the current row. Reach for a stack here and you’ll get a zig-zag through the depths, not a clean row-by-row read. Level-order needs the opposite discipline: first come, first served. It needs a queue.

Seed the queue with the root. Then repeat: pull a node off the front, record it, and push its children onto the back. Because children always join behind the nodes already waiting, a whole level drains before the next one starts.

public List<Integer> levelOrder() {
    List<Integer> out = new ArrayList<>();
    if (root == null) {
        return out;
    }
    Queue<Node> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();          // take from the front
        out.add(node.value);
        if (node.left != null) {
            queue.add(node.left);          // children join the back
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    return out;
}

On our tree this prints 4 2 6 1 3 5 7 — the root, then its row, then the leaves, exactly top-to-bottom and left-to-right. Swap the queue for a stack and that guarantee evaporates. The container is the algorithm.

Step 5: measuring height

Height is the whole performance story, so let’s compute it. The recursion writes itself: a node’s height is one more than the taller of its two children.

The subtlety is the base case, and it’s where a lot of people trip. What’s the height of nothing — an empty tree? Reach for the obvious 0 and watch what happens:

private int height(Node node) {
    if (node == null) {
        return 0;                          // looks right, counts wrong
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

With null returning 0, a lone leaf reports height 1, and our tree reports 3. That’s node counting — the number of nodes on the longest path — not edge counting. Both conventions exist, but the one interviewers usually mean (and the one that makes a single node height 0) counts edges, which means an empty tree is -1:

public int height() {
    return height(root);
}
 
private int height(Node node) {
    if (node == null) {
        return -1;                         // empty tree: -1 edge
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

Now a lone node is 0, and our balanced tree is 2. Whichever convention you pick, state it out loud — a silent off-by-one on height is a classic way to quietly fail a round.

And height is not a fixed property of the values — it’s a property of the shape. Here are the same seven values arranged two ways:

Bushy on the left: height 2. A leaning chain on the right: height 6. Same data, and the right-hand tree is really just a linked list that took a wrong turn. Hold that image — it’s about to become the entire point.

Why in-order comes out sorted

This is the idea worth slowing down for, because it’s where a binary tree stops being a shape and becomes a tool.

So far our tree carried no ordering rule. Add exactly one, and everything changes. A binary search tree (BST) makes a single promise at every node:

Every value in the left subtree is smaller than the node, and every value in the right subtree is larger.

Look back at our tree — it was a BST all along. Left of 4 lives {1, 2, 3}, right of 4 lives {5, 6, 7}. Left of 2 is 1, right is 3. The promise holds everywhere.

Now, why does in-order emerge sorted? Not by luck — it falls straight out of the promise. Recall what in-order does at any node: everything on the left, then the node, then everything on the right. The BST rule says everything on the left is smaller and everything on the right is larger. So at the root you emit (all values < 4), then 4, then (all values > 4) — and by the same argument one level down, that left chunk itself came out sorted, and so did the right. Peel it apart:

A sorted list, then a value bigger than all of it, then a list of values all bigger still, each sorted — glue them and the result is sorted, top to bottom. The base case is the empty subtree (trivially sorted), and induction carries it up to the root. That’s the whole proof, and the diagram is it made visible: drop every node straight down onto a number line and they land 1, 2, 3, 4, 5, 6, 7 — in order, for free. An in-order traversal is nothing but reading the tree left to right.

That single property is why TreeMap and TreeSet exist: they keep keys in a balanced BST, so iterating them is automatically sorted and finding a key is a walk down one path. Building search, insert, and delete on that promise is a topic of its own — the binary search tree.

…and why height is everything

Here’s the catch, and it’s the reason "balanced" is a word you’ll hear for the rest of your career.

Finding a value in a BST is a walk from the root: at each node, go left if you’re smaller, right if you’re larger. So the cost of a search is exactly the length of the path you walk — the height of the tree. On the bushy tree, height is about log₂ n, so search, insert, and delete are all O(log n): a million keys in ~20 comparisons. Beautiful.

But the BST promise says nothing about shape. Insert 1, 2, 3, 4, 5, 6, 7 in that order and every value is larger than the last, so each one hangs off the right — you build the skewed chain from the diagram. It’s still a perfectly valid BST; its in-order is still sorted. But its height is n − 1, so search is now O(n). You’ve paid for a tree and received a linked list.

That inequality is the floor: n nodes cannot be arranged shorter than about log₂ n. A balanced tree lives at that floor; a skewed one sits at the ceiling of n. The ordering is guaranteed by the insert rule — but the height, the thing that makes the ordering fast, is not. Closing that gap is the entire job of self-balancing trees (AVL, red-black), which perform small rotations on the way back up from an insert to keep the tree near that logarithmic floor no matter what order the data arrives in. Every binary tree you’ll rely on in production is really a plain binary tree plus a discipline that keeps it short.

How the shapes compare

Line the tree up against the two structures it’s competing with — a sorted array and a linked list — plus its own worst case, and the reason it exists jumps out. Here n is the number of values:

Read the top-left corner. The balanced BST is the only column that’s O(log n) for search and insert and delete at once. A sorted array searches fast but every insert shoves half the elements over. A linked list splices in O(1) once you’re standing on the spot — but finding the spot is a full O(n) scan. The tree is the structure that refuses to choose: it keeps data ordered and stays cheap to change. And the last column is the standing warning — lose the balance and every one of those wins collapses back to O(n).

The complete implementation

Everything we built, assembled into one class you can whiteboard from memory — recursive pre/in/post-order, a queue-backed level-order, and height:

package dev.fiveyear.tree;
 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
 
public final class BinaryTree {
 
    public static final class Node {
        final int value;
        Node left;
        Node right;
 
        public Node(int value) {
            this.value = value;
        }
 
        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
 
    private final Node root;
 
    public BinaryTree(Node root) {
        this.root = root;
    }
 
    /** Left subtree, then the node, then the right subtree. Sorted on a BST. */
    public List<Integer> inorder() {
        List<Integer> out = new ArrayList<>();
        inorder(root, out);
        return out;
    }
 
    private void inorder(Node node, List<Integer> out) {
        if (node == null) {
            return;
        }
        inorder(node.left, out);
        out.add(node.value);
        inorder(node.right, out);
    }
 
    /** The node first, then its left subtree, then its right subtree. */
    public List<Integer> preorder() {
        List<Integer> out = new ArrayList<>();
        preorder(root, out);
        return out;
    }
 
    private void preorder(Node node, List<Integer> out) {
        if (node == null) {
            return;
        }
        out.add(node.value);
        preorder(node.left, out);
        preorder(node.right, out);
    }
 
    /** Both subtrees first, the node last — children before their parent. */
    public List<Integer> postorder() {
        List<Integer> out = new ArrayList<>();
        postorder(root, out);
        return out;
    }
 
    private void postorder(Node node, List<Integer> out) {
        if (node == null) {
            return;
        }
        postorder(node.left, out);
        postorder(node.right, out);
        out.add(node.value);
    }
 
    /** Level by level, left to right — a breadth-first walk backed by a queue. */
    public List<Integer> levelOrder() {
        List<Integer> out = new ArrayList<>();
        if (root == null) {
            return out;
        }
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            out.add(node.value);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return out;
    }
 
    /** Edges on the longest root-to-leaf path: empty tree -1, a lone node 0. */
    public int height() {
        return height(root);
    }
 
    private int height(Node node) {
        if (node == null) {
            return -1;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

And here it is walking the exact tree we drew:

//         4
//       /   \
//      2     6
//     / \   / \
//    1   3 5   7
BinaryTree.Node root =
    new BinaryTree.Node(4,
        new BinaryTree.Node(2, new BinaryTree.Node(1), new BinaryTree.Node(3)),
        new BinaryTree.Node(6, new BinaryTree.Node(5), new BinaryTree.Node(7)));
 
BinaryTree tree = new BinaryTree(root);
 
tree.preorder();    // [4, 2, 1, 3, 6, 5, 7]
tree.inorder();     // [1, 2, 3, 4, 5, 6, 7]   ← sorted, because it's a BST
tree.postorder();   // [1, 3, 2, 5, 7, 6, 4]
tree.levelOrder();  // [4, 2, 6, 1, 3, 5, 7]
tree.height();      // 2

The interview corner

Binary trees are the most common warm-up in the building, and the fastest way to look senior is to ask before you code.

Clarifying questions worth asking first:

• "Is it a plain binary tree, or a binary search tree?" This decides everything — whether the left-smaller-right-larger promise holds, and therefore whether search, in-order-is-sorted, and range queries are on the table.
• "Can I assume it stays balanced, or could the input skew it?" It’s the difference between the O(log n) you’ll happily claim and the O(n) that’s actually lurking. If skew is possible, a self-balancing tree (or a different structure) may be the real answer.
• "How deep can it get?" A skewed tree of depth 100,000 will blow the recursion stack. If depth is unbounded, plan an iterative traversal with an explicit stack.

The follow-up ladder — where a good interviewer takes it next:

1. "Do it without recursion." → Keep an explicit stack for depth-first, pushing children as you go; or use Morris traversal, which threads the tree to get in-order in O(1) extra space.
2. "Rebuild the tree from its traversals." → Pre-order + in-order (or post-order + in-order) reconstruct it uniquely — the first array names each root, the in-order array splits left from right. Pre + post alone can’t; single-child nodes stay ambiguous.
3. "Keep search O(log n) as data pours in." → A self-balancing BST — AVL or red-black — rotates on insert and delete to pin the height at O(log n) regardless of insertion order.
4. "It won’t fit in RAM." → A B-tree / B+-tree: high fan-out keeps the height around 3–4 even for billions of rows, so a lookup is a handful of disk reads. It’s the shape behind every database index.
5. "Send the tree over the wire, then rebuild it." → Serialize with a pre-order walk that writes a marker for each null, and deserialize by replaying that stream — the classic encode/decode.

Three mistakes that fail the round:

• Forgetting the null base case. No bottom to the recursion means a NullPointerException on the first leaf, or a walk that never ends. Every tree function starts with the empty-tree check.
• Assuming order you weren’t given. Treating a plain binary tree as if it’s sorted, or — more subtly — assuming a BST is balanced. The skew turns your confident O(log n) into a silent O(n), and it only shows up at scale.
• Using the wrong container for level-order. A stack gives you depth-first, not row-by-row. BFS needs a queue — and while you’re at it, say which height convention (edges or nodes) you’re counting, so your answer isn’t off by one.

Where to go from here

You now own the foundation: a value with up to two children, three places to visit it, a queue for going wide, and a height that decides whether search is fast or slow. Three natural next stops, each one a way the base tree grows up:

• Self-balancing BSTs (AVL, red-black). The rotations that keep the height near log n no matter what order the data arrives — turning the worst case back into the best.
• Heaps. A complete binary tree that always hands you the smallest (or largest) value at the root — the priority queue behind Dijkstra’s algorithm and every scheduler.
• B-trees and tries. The bushy, disk-friendly relative behind database indexes, and the trie — a tree keyed by the characters of a word rather than a comparison.

Next time you glance at a bracket and instantly know the champion needs both semifinal winners first, you’ll know you’re reading a post-order traversal — and that the same little shape is quietly sorting your data and finding your row in a database a billion rows deep.