TreesLesson 1

What Is a Tree?

Nodes, edges, root, leaves, depth, height — all the tree terminology, what makes a tree a tree, and binary trees specifically.

What Is It?

A tree is a way to organize data in a hierarchy. Think of a family tree — one person at the top, with branches going downward to their children, grandchildren, and so on.

Every tree has one special starting node called the root — it sits at the top and has no parent. Every other node connects to exactly one parent above it. There are no loops — you can never follow connections and end up back where you started.

The most important kind for coding interviews is the binary tree. In a binary tree, each node can have at most two children — a left child and a right child. That's the only rule.

Analogy

The Family Tree

Imagine tracing your family tree starting from your great-grandmother at the top. She is the root — she has no parent in this tree. Her children are the next level down. Each of her children has their own children, and so on.

Anyone with no children is a leaf — like the youngest generation with no descendants yet. The number of steps from the root down to a specific person is that person's depth. The root has depth 0. Her children have depth 1. Her grandchildren have depth 2.

There are no cycles in a family tree. You can't follow connections and loop back to yourself. Every person has exactly one parent (except the root at the top).

Try It Yourself

Traversals:
8316471014

How It Works

Tree Terminology

Let's nail down every term using this example tree:

pseudocode
1
2
3
4
5
6
7
            A          <-- root (depth 0)
          /   \
        B       C      <-- depth 1
       / \       \
      D   E       F    <-- depth 2
     /           / \
    G           H   I  <-- depth 3
  • Root: A — the topmost node, no parent
  • Parent: B is the parent of D and E
  • Child: D and E are children of B
  • Sibling: D and E are siblings — they share the same parent
  • Leaf: G, E, H, I — nodes with no children
  • Internal node: A, B, C, D, F — nodes that have at least one child
  • Depth of a node: How many steps from the root. A is depth 0, B and C are depth 1, G is depth 3
  • Height of a node: How many steps down to its deepest child. A leaf has height 0. A has height 3.
  • Height of the tree: The height of the root node — 3 in this example
  • Subtree: A node and all its descendants. The subtree at B contains B, D, E, and G

Binary Trees

A binary tree is a tree where every node has at most 2 children, called left and right. That constraint is what makes binary trees so useful — at every node, you make a binary choice: go left or go right.

Every node has three fields:

pseudocode
1
2
3
4
class TreeNode:
    data
    left = null
    right = null

That's it. Three fields. Every binary tree algorithm builds on this.

Building a binary tree manually:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
root = new TreeNode("A")
root.left = new TreeNode("B")
root.right = new TreeNode("C")
root.left.left = new TreeNode("D")
root.left.right = new TreeNode("E")
root.right.right = new TreeNode("F")
​
Result:
        A
       / \
      B   C
     / \   \
    D   E   F

A note on tree shapes

Trees can have different shapes. A balanced tree is roughly the same depth on all sides. A degenerate tree is where every node has just one child — it looks like a linked list standing up. The shape of a tree matters a lot for performance, which you'll see in the next lessons.

Why Trees Matter

Trees show up everywhere in computing:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
FILE SYSTEM                    HTML PAGE
/                              <html>
├── home/                        ├── <head>
│   ├── alice/                   │   └── <title>
│   └── bob/                     └── <body>
└── etc/                             ├── <h1>
    └── config/                      └── <p>
​
ORG CHART                      EXPRESSION TREE
      CEO                            +
     /   \                           / \
   VP1   VP2                        *   3
   / \                             / \
  M1  M2                          2   5
                               Represents: (2 * 5) + 3

Trees are recursive by nature

Here's the most important thing to understand: every node in a tree is itself the root of a smaller tree (called a subtree). This means most tree algorithms are naturally recursive.

The pattern is always the same: handle the null case, do something with the current node, then recurse left and right.

pseudocode
1
2
3
4
5
6
7
8
9
function countNodes(node):
    if node is null:
        return 0
    return 1 + countNodes(node.left) + countNodes(node.right)
​
function height(node):
    if node is null:
        return -1
    return 1 + max(height(node.left), height(node.right))

General Tree

  • A has 3 children: B, C, D
  • B has 2 children: E, F
  • Requires variable-size child list

Each node can have any number of children

natural representation

Left-Child, Right-Sibling

  • firstChild pointer -> leftmost child
  • nextSibling pointer -> next sibling
  • A.firstChild = B, B.nextSibling = C, C.nextSibling = D
  • B.firstChild = E, E.nextSibling = F

Same tree using only two pointers per node

binary tree representation

Examples

Example 1: Calculating height

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
        10
       /  \
      5    15
     /    /  \
    3    12   20
              /
             18
​
height(10):
  height(5):
    height(3): returns 0  (leaf)
    height(null) = -1
    return 1 + max(0, -1) = 1
  height(15):
    height(12): returns 0
    height(20):
      height(18): returns 0
      height(null) = -1
      return 1 + max(0, -1) = 1
    return 1 + max(0, 1) = 2
  return 1 + max(1, 2) = 3
​
Height = 3

Example 2: Counting nodes

pseudocode
1
2
3
4
5
6
7
8
9
10
      A
     / \
    B   C
   /
  D
​
countNodes(A):
  1 + countNodes(B) + countNodes(C)
  1 + (1 + countNodes(D) + 0) + (1 + 0 + 0)
  1 + (1 + 1) + 1 = 4

Example 3: Simple recursive check

pseudocode
1
2
3
4
5
6
7
// Is this tree just a single node (or empty)?
function isSingleOrEmpty(node):
    if node is null:
        return true
    if node.left is null and node.right is null:
        return true   // leaf
    return false

Common Mistakes

  1. Confusing depth and height. Depth is measured going DOWN from the root (root = depth 0). Height is measured going UP from the leaves (a leaf = height 0). They point in opposite directions.
  1. Forgetting the null check in recursion. Every recursive tree function must start with if node is null: return. This is the base case that stops recursion. Without it, you'll get a crash.
  1. Confusing binary trees with binary search trees. A plain binary tree has no ordering rule — any value can go anywhere. A binary search tree (next lesson) adds a sorting rule. Not every binary tree is a BST.
  1. Assuming trees are always balanced. A tree with n nodes could be very tall (if every node has one child) or very short (if it's perfectly balanced). Always think about the worst case.

Best Practices

  • Always handle the null case first in any tree function — it's the foundation of every recursive algorithm
  • Draw the tree before writing code — a quick sketch catches edge cases you'd miss otherwise
  • Think recursively — if you can solve the problem for a single node using answers from its two subtrees, you're done
  • Start with simple problems (count nodes, find height) to build intuition before tackling harder ones
Hash SetsBinary Search Trees