Binary trees

coreCommon atGoogleMetaAmazonMicrosoftRead firstRecursionStacksQueues and dequesPractise in the Sandbox →

A binary tree is a set of nodes where each node has at most a left and a right child, and every node except the root has exactly one parent. You walk it depth-first (preorder, inorder, postorder: a recursion, i.e. a stack) or breadth-first (level order: a queue). Every walk is O(n) time; depth-first uses O(height) extra space, which is O(log n) when balanced and O(n) when it degenerates into a chain.

The idea in plain words

A binary tree is a family tree where everyone has at most two kids. The words you need:

Term	Meaning
root	the one node with no parent
leaf	a node with no children
depth of a node	edges from the root down to it (root has depth 0)
height of a tree	edges on the longest root-to-leaf path. Some books count nodes instead; say which you mean
subtree	a node plus everything below it. It is itself a binary tree
full	every node has 0 or 2 children
complete	every level is full except maybe the last, which fills left to right (a heap is complete)
perfect	every level is full: 2^(h+1) − 1 nodes
balanced	heights of left and right subtrees differ by at most a small amount everywhere, so height is O(log n)

The key insight: a tree is recursive. A node’s left child is the root of a smaller tree. So almost every tree function has the same shape: handle the empty tree, recurse on the left, recurse on the right, combine. The only real decision is when you do the node’s own work relative to the two recursive calls. That decision is the difference between preorder, inorder and postorder.

See it

Pick an order and step through. The highlighted path is the recursion’s call stack: the chain of visit() calls that are still waiting to finish. Switch to level order and the stack becomes a queue. Edit the tree to try a lopsided one or a chain.

Four ways to walk a binary tree

step through

tree, level order (null = gap)

call stack (top ↑)

(empty)

output

·

ruleleft subtree, then node, then right subtree

depth0

currenton the call stackoutput (#order)

inorder: left subtree, then node, then right subtree.

↺◀▶ Play▶1 / 27

Where the three depth-first orders come from

Here’s a way to see all three at once. Trace a line around the outside of the tree, hugging it. You pass every node exactly three times: on the way down (left side), between its two children (underneath), and on the way back up (right side). Preorder records the first pass, inorder the second, postorder the third.

One walk around the tree gives all three orders

step through

tree, level order

pre (pass 1)

·

in (pass 2)

·

post (pass 3)

·

being passed nowpassed, not finishedall three passes done

Trace a line around the tree, hugging it counter-clockwise from the root. Every node gets passed three times.

↺◀▶ Play▶1 / 20

When to reach for it

The problem says…	Traversal	Why
“copy / serialize the tree”, “print the structure top-down”, “pass something from parent to child”	preorder	A node is handled before its subtrees, so it can hand its children information (a depth, a running path).
“in sorted order” on a binary search tree	inorder	Left < node < right, so left-node-right visits keys in ascending order. See BSTs.
“size / sum / height of each subtree”, “delete the tree”, “evaluate an expression tree”	postorder	A node needs its children’s answers before it can compute its own.
“level by level”, “nearest”, “minimum depth”, “per row”	level order	A queue releases all of depth d before any of depth d+1. See BFS.

The question to ask at every node

Most recursive tree problems become simple once you answer: “what does this function return for a subtree, and how do I combine the left and right answers?” If you also need to send something down (a bound, a depth, a path so far), pass it as a parameter. Information that flows down is preorder-shaped; information that flows up is postorder-shaped.

How it works

Recursive depth-first traversals

1. If the node is empty, return. This base case is what stops the recursion at every missing child.
2. Recurse into the left subtree.
3. Recurse into the right subtree.
4. Do the node’s work before step 2 (preorder), between 2 and 3 (inorder), or after 3 (postorder).

Python

traversals.py

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class Node:
    val: int
    left: Node | None = None
    right: Node | None = None


def preorder(n: Node | None, out: list[int]) -> list[int]:
    if n:
        out.append(n.val)          # 1. node first
        preorder(n.left, out)      # 2. then the whole left subtree
        preorder(n.right, out)     # 3. then the whole right subtree
    return out


def inorder(n: Node | None, out: list[int]) -> list[int]:
    if n:
        inorder(n.left, out)
        out.append(n.val)          # node between its subtrees: sorted order in a BST
        inorder(n.right, out)
    return out


def postorder(n: Node | None, out: list[int]) -> list[int]:
    if n:
        postorder(n.left, out)
        postorder(n.right, out)
        out.append(n.val)          # node last: children are "done" before the parent
    return out


if __name__ == "__main__":
    #        4
    #      2   6
    #     1 3 5 7
    t = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
    assert preorder(t, []) == [4, 2, 1, 3, 6, 5, 7]
    assert inorder(t, []) == [1, 2, 3, 4, 5, 6, 7]
    assert postorder(t, []) == [1, 3, 2, 5, 7, 6, 4]
    assert inorder(None, []) == []
    print("ok")

TypeScript

traversals.ts

import assert from "node:assert/strict";

export interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null }
export const node = (val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode => ({ val, left, right });

export function preorder(n: TreeNode | null, out: number[] = []): number[] {
  if (n) {
    out.push(n.val); // 1. node first
    preorder(n.left, out); // 2. then the whole left subtree
    preorder(n.right, out); // 3. then the whole right subtree
  }
  return out;
}

export function inorder(n: TreeNode | null, out: number[] = []): number[] {
  if (n) {
    inorder(n.left, out);
    out.push(n.val); // node between its subtrees: sorted order in a BST
    inorder(n.right, out);
  }
  return out;
}

export function postorder(n: TreeNode | null, out: number[] = []): number[] {
  if (n) {
    postorder(n.left, out);
    postorder(n.right, out);
    out.push(n.val); // node last: children are "done" before the parent
  }
  return out;
}

//        4
//      2   6
//     1 3 5 7
const t = node(4, node(2, node(1), node(3)), node(6, node(5), node(7)));
assert.deepEqual(preorder(t), [4, 2, 1, 3, 6, 5, 7]);
assert.deepEqual(inorder(t), [1, 2, 3, 4, 5, 6, 7]);
assert.deepEqual(postorder(t), [1, 3, 2, 5, 7, 6, 4]);
assert.deepEqual(inorder(null), []);
console.log("ok");

C#

traversals.cs

//        4
//      2   6
//     1 3 5 7
var t = new Node(4, new(2, new(1), new(3)), new(6, new(5), new(7)));
Check(Preorder(t, []), [4, 2, 1, 3, 6, 5, 7]);
Check(Inorder(t, []), [1, 2, 3, 4, 5, 6, 7]);
Check(Postorder(t, []), [1, 3, 2, 5, 7, 6, 4]);
Check(Inorder(null, []), []);
Console.WriteLine("ok");

static List<int> Preorder(Node? n, List<int> output)
{
    if (n is null) return output;
    output.Add(n.Val);              // 1. node first
    Preorder(n.Left, output);       // 2. then the whole left subtree
    Preorder(n.Right, output);      // 3. then the whole right subtree
    return output;
}

static List<int> Inorder(Node? n, List<int> output)
{
    if (n is null) return output;
    Inorder(n.Left, output);
    output.Add(n.Val);              // node between its subtrees: sorted order in a BST
    Inorder(n.Right, output);
    return output;
}

static List<int> Postorder(Node? n, List<int> output)
{
    if (n is null) return output;
    Postorder(n.Left, output);
    Postorder(n.Right, output);
    output.Add(n.Val);              // node last: children are "done" before the parent
    return output;
}

static void Check(List<int> got, int[] want)
{
    if (!got.SequenceEqual(want)) throw new Exception($"got {string.Join(",", got)}");
}

record Node(int Val, Node? Left = null, Node? Right = null);

Iterative versions: inorder with a stack, level order with a queue

Recursion hides a stack. Making it explicit avoids stack overflows on deep trees (Python’s default recursion limit is about 1000) and is a common follow-up.

1. Inorder: walk left as far as possible, pushing every node you pass.
2. Pop: that’s the leftmost node you haven’t output. Output it.
3. Move to its right child and repeat from step 1.
4. Level order: put the root in a queue. Repeatedly take from the front, output it, and add its children to the back.

Python

iterative.py

from __future__ import annotations
from collections import deque
from dataclasses import dataclass


@dataclass
class Node:
    val: int
    left: Node | None = None
    right: Node | None = None


def inorder_iter(root: Node | None) -> list[int]:
    out: list[int] = []
    stack: list[Node] = []           # the call stack, made explicit
    n = root
    while n or stack:
        while n:                     # 1. dive left, remembering the way back
            stack.append(n)
            n = n.left
        n = stack.pop()              # 2. leftmost unvisited node: output it
        out.append(n.val)
        n = n.right                  # 3. then do the same for its right subtree
    return out


def level_order(root: Node | None) -> list[int]:
    out: list[int] = []
    q = deque([root] if root else [])
    while q:
        n = q.popleft()              # FIFO: everything on depth d leaves before depth d+1
        out.append(n.val)
        if n.left:
            q.append(n.left)
        if n.right:
            q.append(n.right)
    return out


if __name__ == "__main__":
    t = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
    assert inorder_iter(t) == [1, 2, 3, 4, 5, 6, 7]
    assert level_order(t) == [4, 2, 6, 1, 3, 5, 7]
    # A 100k-deep chain would blow Python's recursion limit (~1000); the loop doesn't care.
    chain = None
    for v in range(100_000, 0, -1):
        chain = Node(v, chain)
    assert inorder_iter(chain)[:3] == [100_000, 99_999, 99_998]
    assert level_order(None) == []
    print("ok")

TypeScript

iterative.ts

import assert from "node:assert/strict";
import { node, type TreeNode } from "./traversals.ts";

export function inorderIter(root: TreeNode | null): number[] {
  const out: number[] = [];
  const stack: TreeNode[] = []; // the call stack, made explicit
  let n = root;
  while (n || stack.length) {
    while (n) { // 1. dive left, remembering the way back
      stack.push(n);
      n = n.left;
    }
    n = stack.pop()!; // 2. leftmost unvisited node: output it
    out.push(n.val);
    n = n.right; // 3. then do the same for its right subtree
  }
  return out;
}

export function levelOrder(root: TreeNode | null): number[] {
  const out: number[] = [];
  const q: TreeNode[] = root ? [root] : [];
  // Index pointer instead of q.shift(): shift is O(n) on JS arrays.
  for (let head = 0; head < q.length; head++) {
    const n = q[head]; // FIFO: everything on depth d leaves before depth d+1
    out.push(n.val);
    if (n.left) q.push(n.left);
    if (n.right) q.push(n.right);
  }
  return out;
}

const t = node(4, node(2, node(1), node(3)), node(6, node(5), node(7)));
assert.deepEqual(inorderIter(t), [1, 2, 3, 4, 5, 6, 7]);
assert.deepEqual(levelOrder(t), [4, 2, 6, 1, 3, 5, 7]);
let chain: TreeNode | null = null; // deep enough to overflow a recursive version
for (let v = 100_000; v >= 1; v--) chain = node(v, chain);
assert.deepEqual(inorderIter(chain).slice(0, 3), [100_000, 99_999, 99_998]);
assert.deepEqual(levelOrder(null), []);
console.log("ok");

C#

iterative.cs

var t = new Node(4, new(2, new(1), new(3)), new(6, new(5), new(7)));
if (!InorderIter(t).SequenceEqual([1, 2, 3, 4, 5, 6, 7])) throw new Exception("inorder");
if (!LevelOrder(t).SequenceEqual([4, 2, 6, 1, 3, 5, 7])) throw new Exception("level order");
Node? chain = null;                                 // deep enough to overflow a recursive version
for (int v = 100_000; v >= 1; v--) chain = new Node(v, chain);
if (InorderIter(chain)[0] != 100_000) throw new Exception("chain");
if (LevelOrder(null).Count != 0) throw new Exception("empty");
Console.WriteLine("ok");

static List<int> InorderIter(Node? root)
{
    var output = new List<int>();
    var stack = new Stack<Node>();                  // the call stack, made explicit
    var n = root;
    while (n is not null || stack.Count > 0)
    {
        for (; n is not null; n = n.Left) stack.Push(n); // 1. dive left, remembering the way back
        n = stack.Pop();                            // 2. leftmost unvisited node: output it
        output.Add(n.Val);
        n = n.Right;                                // 3. then do the same for its right subtree
    }
    return output;
}

static List<int> LevelOrder(Node? root)
{
    var output = new List<int>();
    var q = new Queue<Node>();
    if (root is not null) q.Enqueue(root);
    while (q.Count > 0)
    {
        var n = q.Dequeue();                        // FIFO: depth d leaves before depth d+1
        output.Add(n.Val);
        if (n.Left is not null) q.Enqueue(n.Left);
        if (n.Right is not null) q.Enqueue(n.Right);
    }
    return output;
}

record Node(int Val, Node? Left = null, Node? Right = null);

Processing one level at a time

For “per level” questions, read len(queue) at the start of each round and pop exactly that many nodes. Those are precisely the nodes on the current level; their children form the next.

What it costs

	Time	Extra space
Any traversal	O(n): each node entered once, left once
Recursive / stack-based DFS	O(n)	O(h), where h is the height
Level order (BFS)	O(n)	O(w), where w is the widest level (up to about n/2 in a perfect tree)
Balanced tree		h = O(log n)
Degenerate tree (a chain)		h = n − 1, so DFS uses O(n) space
Morris traversal (threaded)	O(n)	O(1), by temporarily rewiring null right pointers

The space trade-off between DFS and BFS flips with shape. A tall skinny tree is cheap for BFS and expensive for DFS; a short bushy tree is the reverse.

Variations you’ll meet

• N-ary trees. Same traversals with a loop over children instead of left/right. Inorder only makes sense for binary trees.
• Trees with parent pointers. You can walk upward, which turns some problems into “find where two paths meet”.
• Trees given as arrays. Level order with null gaps (the format the visualization accepts), or the implicit 2i+1 / 2i+2 layout of a heap.
• Rebuilding a tree. Preorder + inorder (or postorder + inorder) determine a tree with distinct values uniquely. Preorder alone does not.
• Expression trees. Operators in internal nodes, operands in leaves. Postorder evaluates; inorder with parentheses prints. See expression evaluation.

Pitfalls

• Forgetting the empty tree. Decide what f(None) returns before writing anything else. It’s the base case of every recursion.
• Confusing depth and height, or edges and nodes. A one-node tree has height 0 in edges and 1 in nodes. Ask or state your convention.
• Recursion depth. A 100,000-node chain overflows the call stack in Python, and can in C# and JS too. Use an explicit stack if inputs can be deep.
• queue.shift() in JavaScript is O(n). Use a head index (as in the sample) or a real deque.
• Mixing up “balanced” and “complete” or “BST”. A binary tree has no ordering rule at all unless the problem says it’s a search tree.
• Mutating while traversing (e.g. swapping children) without being clear whether you’ve already visited the swapped child.

In the interview

• Ask: can it be empty? can values repeat? is it a BST or just a binary tree? how deep can it get?
• Say the recursion contract out loud: “f(node) returns the X of the subtree rooted at node. For an empty tree it’s Y. Otherwise it combines f(left) and f(right) like this.”
• Give space as O(h) and then say what h is in the worst and balanced cases.
• Expect follow-ups: “Do it without recursion”, “Do it level by level”, “What if the tree has a billion nodes on disk?” (streaming traversal, O(h) memory), “What if nodes have parent pointers?”

Check yourself

Check yourself

pick one

You need to compute the total file size of every folder in a directory tree. Which traversal order fits?

APreorderBInorderCPostorderDLevel order

Check yourself

pick one

A recursive inorder traversal of a binary tree with n nodes is O(n) time. What is its extra space in the worst case?

AO(1)BO(log n)CO(n)DO(n log n)

Check yourself

pick one

You're given only the preorder sequence [1, 2, 3] of a binary tree with distinct values. How many different trees produce it?

AExactly oneBTwoCFiveDInfinitely many

Practice on your own

These are classic textbook exercises, not gym questions:

• Count the leaves of a binary tree, recursively and then with an explicit stack.
• Check whether a tree is a mirror image of itself (symmetric).
• Invert a binary tree (swap every node’s children).
• Does any root-to-leaf path sum to a given target?
• Rebuild a tree from its preorder and inorder sequences.

Go deeper

• CLRS, ch. 12.1 (tree walks) and ch. 10.4 (representing rooted trees).
• Sedgewick and Wayne, Algorithms §3.2, Binary Search Trees: recursive tree code done cleanly.
• cp-algorithms: Euler tour technique, the “walk around the tree” view used above, applied to ancestor queries.
• Knuth, The Art of Computer Programming Vol. 1, §2.3.1, “Traversing binary trees”, including threaded (Morris-style) traversal.

Related

Binary search treesAdd an ordering rule and inorder becomes sorted order.

Depth-first searchThe same walk on general graphs, with a visited set.

Breadth-first searchLevel order, generalized.

RecursionBase cases, contracts, and the call stack.