24.01Intermediate / Advanced12 topics14 min9 interactive animations

Tree anatomy

The vocabulary of trees: root, parent, child, leaf, edge, height, depth, level, degree, subtree, forest, and how binary trees differ from general trees.

Learning goals

Name every part of a tree and point to it in a drawing
Tell depth, height and level apart and compute each
Explain why a tree with n nodes has n - 1 edges
Distinguish binary trees, general trees and forests

Prerequisites

Recursion and divide-and-conquer fundamentalsLinked lists

Trees describe anything with a hierarchy: folders, HTML, organisation charts, expression syntax, search indexes. The words below are used in every tree problem, so it pays to fix them exactly once.

24.01.1

Root

The **root** is the single node with no parent, the entry point from which every other node is reached by following child links. A tree is always held by a reference to its root: lose it and the tree is gone. An empty tree has no root (the reference is null).

Run the animation on the “The root” preset: the first frame highlights node 1 as the root, and its summary reports depth 0 and height 3, the height of the whole tree.

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.2

Parent

A node's **parent** is the node directly above it, the one whose child it is. Every node except the root has exactly one parent, and that is what makes a hierarchy a tree and not a general graph: following parents from any node always leads to the root, without a choice or a cycle.

In most Java node classes there is no parent field: nodes only point down. When an algorithm needs the parent it tracks it on the way down, or stores a Map<TreeNode, TreeNode> built in one traversal.

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.3

Child

The **children** of a node are the nodes directly below it. In a binary tree a node has a left child, a right child, both or neither, and *which* side matters: a left child alone and a right child alone are different trees.

Children sharing a parent are **siblings**. In the “An internal node” preset, the animation shows node 2's two children and, in the following frame, 2's sibling 3. The ancestors of a node are the nodes on the path up to the root, and its descendants are everything in the subtrees below it.

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.4

Leaf

A **leaf** is a node with no children; a node with at least one child is **internal**. Leaves are where recursion on trees stops, and many questions reduce to them: root-to-leaf paths, leaf counts, boundary traversals.

A binary tree with n nodes has n + 1 empty child links in total (each of the n nodes has two child slots, and only n - 1 of the 2n slots are filled by an actual child). In a binary tree where every internal node has two children, the number of leaves is one more than the number of internal nodes.

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.5

Edge

An **edge** is the link between a parent and a child. Every node except the root contributes exactly one edge to its parent, so a tree with n nodes has exactly n - 1 edges. That also explains why a tree is *minimally connected*: one edge fewer and a node would be cut off, one more would make a cycle.

A **path** is a sequence of nodes connected by edges, and the length of a path is its number of edges, not its number of nodes. The distinction matters in the definitions of depth, height and diameter below.

Fact about a tree with n nodes	Value
Edges	n - 1
Paths between two chosen nodes	exactly 1
Empty child links in a binary tree	n + 1

24.01.6

Height

The **height** of a node is the number of edges on the longest downward path from it to a leaf. A leaf has height 0, and the height of a tree is the height of its root. In this course an empty tree has height -1, which makes the recurrence height(n) = 1 + max(height(left), height(right)) work for leaves without a special case.

Some books count nodes instead of edges and give a leaf height 1. Always check which convention a problem statement uses. In the “The root” preset, the root of the 7-node example has height 3.

Java

1static int height(TreeNode n) {
2    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
3    return 1 + Math.max(height(n.left), height(n.right));
4}

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.7

Depth

The **depth** of a node is the number of edges on the path from the root down to it. The root has depth 0, its children depth 1, and so on. Depth looks upward and height looks downward, and the two do not have to add up to a constant: in the “A leaf” preset, node 7 has depth 3 and height 0, while the root has depth 0 and height 3.

Depth is usually computed on the way down by passing depth + 1 to each recursive call, so no separate search is needed.

Java

1// depth of the node with the given value, or -1 if it is absent
2static int depth(TreeNode n, int value, int d) {
3    if (n == null) return -1;
4    if (n.val == value) return d;
5    int left = depth(n.left, value, d + 1);
6    return left >= 0 ? left : depth(n.right, value, d + 1);
7}

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.8

Level

A **level** is the set of nodes at the same depth. The root alone is level 0 in code that numbers from zero, or level 1 in books that number from one; the animation shows the one-based number, depth + 1. Level-order traversal visits one level completely before the next.

The number of nodes on level d of a binary tree is at most 2^d, so a binary tree of height h has at most 2^(h+1) - 1 nodes in total and at most 2^h leaves. Equivalently, a tree with n nodes has height at least ⌊log2 n⌋, which is the lower bound for balanced trees.

Height h	0	1	2	3	4
Most nodes (2^(h+1) - 1)	1	3	7	15	31
Most leaves (2^h)	1	2	4	8	16

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.9

Degree

The **degree** of a node is its number of children; the degree of a tree is the largest degree of any node. A leaf has degree 0 and every node of a binary tree has degree at most 2. (In graphs, 'degree' also counts the edge to the parent, so check the context.)

Run the “An internal node” preset: node 2 has two children, so its degree is 2. The “A chain (degenerate)” preset is a tree where every node has degree 1 apart from the last: it behaves like a linked list, and its height is n - 1.

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.10

Subtree

Every node is the root of a **subtree**: itself plus all its descendants. This is what makes recursion natural on trees, since a subtree is again a tree and a problem about a tree can be split into the same problem on the subtrees of its children.

The animation's “An internal node” preset highlights node 2's subtree: 4 nodes (2, 4, 5 and 7). The size of a subtree is also the quantity stored in the augmented trees of later chapters, where each node keeps its subtree's size to answer rank questions.

Java

1static int subtreeSize(TreeNode n) {
2    return n == null ? 0 : 1 + subtreeSize(n.left) + subtreeSize(n.right);
3}

Tree vocabulary: depth, height, degree, ancestors and subtrees

Interactive · edit the input

binary tree · 5 nodes

RootAncestorChosen nodeChildSiblingRest of its subtree

Setup

The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.

Step 1 / 7

Java

1static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
2static int height(TreeNode n) {
3    if (n == null) return -1;                    // empty tree: -1, so a leaf has height 0
4    return 1 + Math.max(height(n.left), height(n.right));
5}
6static int depth(TreeNode root, TreeNode target, int d) {
7    if (root == null) return -1;
8    if (root == target) return d;                // edges from the root
9    int l = depth(root.left, target, d + 1);
10    return l >= 0 ? l : depth(root.right, target, d + 1);
11}
12static int size(TreeNode n) { return n == null ? 0 : 1 + size(n.left) + size(n.right); }   // nodes in the subtree
13static int degree(TreeNode n) { return (n.left != null ? 1 : 0) + (n.right != null ? 1 : 0); }

Live state

nodes

tree height

leaves

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	nodes=5 tree height=2 leaves=3	The tree has 5 nodes, 3 leafs (nodes without children) and height 2 (edges on its longest root-to-leaf path). The root 3 is the only node with no parent.
2	L8	depth=0 level=1	Walk down: node 3 is 0 edges from the root.
3	L8	depth=1 level=2	Reached node 20: 1 edge below the root, so its depth is 1 and it is on level 2.
4	L13	degree=2 parent=3	20 has 2 childs: 15 and 7; the number of children is its degree (2). Its parent is 3.
5	L13	siblings=1	Sibling: 9, the other child of 3.
6	L12	subtree size=3	The subtree rooted at 20 is the node together with all its descendants: 3 nodes. Every node roots a subtree of its own.
7	L3	depth=1 level=2 height=1 degree=2 subtree size=3	Node 20 is an internal node: depth 1, height 1 (edges down to its deepest leaf), degree 2, subtree of 3 nodes.

24.01.11

Forest

A **forest** is a collection of disjoint trees. Removing the root of a tree leaves a forest of its child subtrees, and removing edges from a tree also gives a forest. Graph algorithms meet forests constantly: the components of an acyclic graph, or the result of a minimum spanning forest on a disconnected graph.

A forest of k trees with n nodes in total has n - k edges. In data-structure code a forest is held as a list of roots; a parent array with several entries equal to -1 is another representation (the last group of this chapter).

24.01.12

Binary vs general trees

In a **binary tree** every node has at most two children, named left and right. In a **general tree** a node may have any number of children, usually stored as a list. Binary trees are the default in algorithms because their code is small and uniform, and because every general tree can be converted to one (the first-child / next-sibling encoding at the end of this chapter).

Special binary trees to know: a **full** tree has 0 or 2 children for every node; a **perfect** tree has all leaves on one level; a **complete** tree is full on every level except possibly the last, which fills from the left (the shape of heaps); a **degenerate** tree has one child per internal node, so it is a list in disguise; a **balanced** tree keeps its height close to log n.

Shape	Rule	Height for n nodes
Perfect	all leaves on one level, every internal node has 2 children	log2(n + 1) - 1
Complete	full except the last level, filled left to right	⌊log2 n⌋
Balanced	subtree heights differ by at most 1 everywhere	O(log n)
Degenerate	every internal node has one child	n - 1

Practice ladder

Now try it yourself

Easy

Maximum Depth of Binary Tree
Same Tree

Medium

Minimum Depth of Binary Tree
Count Complete Tree Nodes

Advanced

Check Completeness of a Binary Tree
Maximum Width of Binary Tree

Key takeaways

A tree has one root, every other node has exactly one parent, and n nodes have n - 1 edges.
Depth counts edges down from the root; height counts edges down to the deepest leaf; a leaf has height 0.
Every node roots a subtree, which is why recursion fits trees.
A binary tree of height h holds at most 2^(h+1) - 1 nodes, so a tree with n nodes has height at least ⌊log2 n⌋.