---
title: "Tree Basics"
description: "Root, child, height, and the three traversal orders — the vocabulary of trees."
source: https://vizlearn.app/algorithms/data-structures/tree-basics
---

# Tree Basics

A tree is a set of nodes joined by parent-to-child edges, with exactly one node — the **root** — that has no parent, and no cycles anywhere. Every other node has exactly one parent, so there is precisely one path from the root to any node. That single rule gives you the whole vocabulary: root, child, parent, leaf, depth, height, subtree.

Lists are linear and graphs can tangle; a tree is the structure in between, and it is the shape underneath file systems, the HTML on this page, database indexes, and almost every "search" data structure you will meet next.

Hold a real tree upside down. The root is at the top, branches fan *downward*, and the tips at the bottom — nodes with no children — are the **leaves**. Two measurements get confused constantly, and separating them is the whole point of this lesson: a node's **depth** is how far *down* from the root it sits, while the tree's **height** is how far down its *deepest* leaf reaches. Same tree, two directions of counting.

## What a Tree Is Made Of

A node holds a value and links to its children — here, a left child and a right child, so this is a **binary** tree (at most two children each). Follow the links downward and you never come back to where you started; that "no cycles, one parent each" property is exactly what separates a tree from a general graph.

The named parts are worth saying out loud, because every later tree lesson assumes them:

- **Root** — the one node with no parent. The search always starts here.
- **Leaf** — a node with no children. The branches end here.
- **Internal node** — any node that *has* at least one child (so: not a leaf).
- **Subtree** — pick any node, take it together with all of its descendants, and you have a tree in its own right. Recursion on trees works precisely because every child *is* the root of a subtree.

We label the nodes with letters (A, B, C, …) on purpose. A plain tree has no ordering rule — a child is not "less than" or "greater than" its parent. Numbers would quietly suggest a binary *search* tree, which is a different, later topic; letters keep the structure honest.

## Tree Basics Step by Step

The default tree (the **Lopsided** shape) is deliberately uneven so it shows every part at once:

```
        A
      /   \
     B     C
    / \   /
   D   E F
      /
     G
```

So `A → B, C`; `B → D, E`; `C → F`; `E → G`. That is seven nodes. D, F, and G are leaves (no children); A, B, C, and E are internal. C has only one child and B has two — real trees are lumpy like this, not perfectly full.

1. **Reveal the root.** A tree starts at a single node, A — the root, the only node with no parent.
2. **Grow it level by level.** A's children B and C appear, joined by edges; then B's children D and E and C's child F; finally E's child G. Each downward link is an **edge**, and the whole thing is seven nodes with no cycle.
3. **Name the leaves.** D, F, and G have no children — they are the leaves, where the branches stop.
4. **Read off depth, top-down.** Depth counts edges from the root *down* to a node. A is depth 0. B and C are one edge below → depth 1. D, E, and F are depth 2. G is depth 3 — the deepest node in the tree.
5. **Read off height.** The tree's height is the depth of its deepest leaf, found by following the longest root-to-leaf path: A → B → E → G, three edges long. So **height = 3**. Notice it equals the largest depth — that is not a coincidence, it is the definition.
6. **See that shape, not count, sets the height.** The animation then rearranges the *same seven nodes* into three shapes side by side: a *balanced* tree just two levels deep (height 2), this lopsided tree (height 3), and a single-child *vine* six levels deep (height 6). Same data, heights from 2 to 6 — height is a fact about the tree's shape, not its node count.

That is the takeaway in one line: **depth is measured from the root down to a node; height is measured from a node down to its deepest leaf; and a tree's height is just the largest depth it contains.** Depth is a property of a *node*; height is a property of a *tree* (or a subtree).

## Same Seven Nodes, Height 2 or Height 6

Seven nodes can be arranged into wildly different heights, and the **Balanced** and **Degenerate** presets make the contrast concrete with the *same seven nodes*:

- **Balanced** — a perfect tree where every level is full. Height is only **2**. No arrangement of seven nodes has a smaller height.
- **Degenerate** — every node except the last has just one child, so the tree is a single chain: a "vine" of height **6** (that is `n − 1`). It has stopped being a useful tree and become a linked list wearing tree clothes.

Same data, opposite shape, height 2 versus height 6 — and since a search-tree lookup, insert, or delete walks one root-to-leaf path and costs time proportional to the height, that gap is the difference between fast and slow. (A full traversal is different: it visits all `n` nodes whatever the shape.) This is the entire reason self-balancing trees (AVL, red-black) exist: they fight to keep the height near the balanced ideal so the degenerate case never happens.

## The Three Traversal Orders

A tree is only useful if you can *visit* its nodes. The natural way is recursive: handle this node, then recurse into the left subtree, then the right. The one decision left is *when* you do the "visit" — and that single choice names the three standard orders:

```python
def traverse(node):
    if node is None:
        return
    # preorder:  visit here  -> node before its subtrees
    traverse(node.left)
    # inorder:   visit here  -> between left and right
    traverse(node.right)
    # postorder: visit here  -> node after its subtrees
```

Run all three on the default tree and you get three different sequences from the same structure:

- **Preorder** (node, then left, then right): `A B D E G C F`. The root comes out first; you see each subtree's root before its contents. This is how you'd copy a tree or print a nested outline.
- **Inorder** (left, then node, then right): `D B G E A F C`. The node falls *between* its two subtrees.
- **Postorder** (left, then right, then node): `D G E B F C A`. Every node appears *after* all its descendants — the order you'd use to delete a tree or compute each subtree's size, because a parent waits for its children to be finished first.

All three visit every node exactly once; they only disagree on order. This lesson shows you *what* each order produces — the dedicated traversal lesson takes apart *how* the recursion produces it, frame by frame on the call stack.

## Edge Cases

- **A single node** — the root is also a leaf. Its depth is 0 and the tree's height is 0. (A tree with no nodes at all is usually given height −1, so that a one-node tree works out to `1 + (−1) = 0` under the recursive height formula.)
- **A node with one child** — perfectly legal. C in the default tree has only a left child. "Binary" caps children at two; it does not require two.
- **The degenerate chain** — when every non-leaf node has one child, height is `n − 1` and the tree behaves like a list. This is the worst case the balanced presets are defined against.
- **Leaves at different depths** — there is no rule that leaves line up. D and F sit at depth 2 while G hangs lower at depth 3.

## Common Mistakes

1. **Swapping depth and height.** Depth is counted from the root *down to a node*; height is counted from a node *down to its deepest leaf*. A node deep in the tree has large depth but possibly height 0 (if it's a leaf). They meet only at the extreme: the tree's height equals the depth of its deepest node.
2. **Reading a plain tree as a search tree.** Here a left child is not "smaller" than its parent — there is no ordering rule at all. That ordering is an *extra* invariant a binary search tree adds on top; this lesson deliberately uses letters so you don't assume it.
3. **Thinking a leaf must be at the bottom level.** A leaf is any node with no children, wherever it sits. The default tree's leaves live at two different depths.
4. **Confusing the three traversal orders.** The node's data comes out before, between, or after its subtrees — that's the only difference, but it changes the entire output sequence and which problems each order solves.
5. **Assuming trees are always balanced.** Nothing stops a plain tree from degenerating into a chain. Keeping height small is a *guarantee you have to build in* (that's what AVL and red-black trees are for), not something you get for free.