Introduction to Binary Trees

You’ve used a dozen trees today without naming one: your file system’s folders, this web page’s DOM, the JSON an API returned, the index that made your database query fast. They’re all the same structure. Learn to manipulate it once — and the recursion that makes it effortless — and a huge slice of computer science suddenly reads like a sentence.

A tree is a hierarchical data structure built from nodes connected by edges, with one special node at the top called the root. Every other node has exactly one parent. There are no cycles — you can’t follow edges and end up back where you started.

That single rule (one parent per non-root node, no cycles) is what separates a tree from the more general graph we’ll meet on Day 9.

Binary trees

A binary tree is the most common tree in interviews: every node has at most two children, conventionally called left and right.

A perfectly-shaped binary tree

The empty tree is a valid tree (zero nodes). A tree with one node is a valid tree (just the root). From there, every node can have 0, 1, or 2 children — that’s it.

The vocabulary you’ll see everywhere

Every tree problem uses these terms. Memorize them now and you’ll stop tripping over the language.

Root, leaf, internal node

Root — the topmost node. It has no parent.
Leaf — a node with no children. The “tips” of the tree.
Internal node — any non-leaf node (the root counts if it has children).

In the tree above, 1 is the root; 4, 5, 6, 7 are leaves; 2 and 3 are internal nodes.

Parent, child, sibling, ancestor, descendant

Parent / child — direct relationship along one edge.
Siblings — two nodes that share the same parent.
Ancestor — any node on the path between a node and the root (including itself if you allow it).
Descendant — any node “below” a given node (the node itself plus everything in its subtree).

In the tree above, 4 and 5 are siblings, both children of 2. 1, 2 are ancestors of 4. 2, 4, 5 are descendants of 2.

Depth, level, and height — the most-confused pair

Depth of a node = number of edges from the root to that node. The root has depth 0.
Level of a node = depth + 1. (Some texts use level = depth; check before answering.)
Height of a node = number of edges in the longest path from that node down to any leaf. A leaf has height 0.
Height of the tree = height of the root.

        1   ← depth 0, height 2
       / \
      2   3 ← depth 1, height 1
     / \
    4   5  ← depth 2, height 0 (leaves)

The classic interview slip-up: “what’s the height of an empty tree?” Different sources answer -1, 0, or “undefined.” Stick to a convention up front (we’ll use 0) and be explicit in your code.

Subtree

A subtree rooted at node X is X plus all of X’s descendants. Every node is the root of its own subtree. This is why recursion works so beautifully — a subtree is just a smaller tree.

Degree

The degree of a node = the number of its children (0, 1, or 2 in a binary tree). A binary tree’s defining property is that every node has degree ≤ 2.

How we store a binary tree in code

Two common representations:

1. Linked nodes (the natural choice)

Each node is an object with a value and pointers (or references) to its left and right children.

This is what every LeetCode binary-tree problem hands you.

2. Array (the heap trick)

For a complete binary tree (no gaps, filled level-by-level), you can store it in a flat array using index arithmetic:

Predict first

Store the tree as the array [1, 2, 3, 4, 5, 6, 7]. The value 2 sits at index 1. With no pointers — just index math — where do its two children live?

Relationship	Formula
Root	index 0
Parent of i	`(i - 1) / 2`
Left child of i	`2 * i + 1`
Right child of i	`2 * i + 2`

tree = [1, 2, 3, 4, 5, 6, 7]

index 0  1  2  3  4  5  6
value 1  2  3  4  5  6  7

                1            ← index 0
              /   \
            2       3        ← indices 1, 2
           / \     / \
          4   5   6   7      ← indices 3-6

This trick is the foundation of heaps (Day 7). It only works cleanly for complete trees — sparse trees waste a lot of array slots if you try it.

Recall the navigation formulas — fill in the child and parent math:

python · fill in the blanks0/2 hints

def left_child(i):
  # ??? index arithmetic (no pointers)
 
def right_child(i):
  return 2 * i + 2
 
def parent(i):
  # ??? index arithmetic (no pointers)

Why trees show up everywhere

A handful of places you’ve already touched a tree without naming it:

File systems — folders contain folders contain files. A literal tree.
HTML / DOM — every web page is a tree. <html> is the root.
JSON / XML — nested data is a tree.
Expression evaluation — (2 + 3) * 4 is an expression tree where leaves are values and internal nodes are operators.
The call stack — recursive function calls form a call tree.
Decision trees — every “yes/no/maybe” flowchart is a tree.
Databases — B-trees back almost every relational database index.
Compilers — abstract syntax trees, parse trees, control-flow graphs.
Game AI — minimax, alpha-beta, Monte Carlo Tree Search — all operate on game trees.

If you can manipulate a tree comfortably, you can read half of computer science.

Quick check

A binary tree has 7 leaves. What's the minimum number of internal nodes it could have?

In the linked-node representation, what does `root->left->right->val` give you?

You’ve got the structure and both representations. Next: tree types — full, complete, perfect, balanced, and degenerate — and why the shape of a tree decides whether its operations are O(log n) or a disappointing O(n).

Overview Tree Types

Finished this page?