Trees: Concepts, Properties, Traversals

Folders on your laptop, a company org chart, the HTML of every web page: all of them are trees. Learn the vocabulary once and half of the algorithms ahead will read like plain English.

★ Lecture: trees_Intro1 · Zaza Gamezardashvili▶ video beginner⏱ 20 min read

←Builds on

0Recursion & the Call StackEvery tree traversal is the same function called recursively on each child.4Generating Subsets & PermutationsThe decision tree of complete search was already a tree; now we name its parts.3Linked ListsA tree node is a linked list node with several next pointers instead of one.

Leads to→

5Binary Search TreeAn in-order traversal of a BST lists its keys in sorted order.5Binary Heap & Priority QueueA heap is a complete binary tree where every parent is smaller than its children.5Trie & AutocompleteA trie is a rooted tree where every edge carries one letter.6Graph RepresentationsA tree is a connected graph without cycles; graphs simply drop that restriction.6Breadth-First Search (BFS)On a tree BFS is the level order traversal; on a graph it adds a visited array.6Tree Diameter & CenterDiameter and center are built from depth, height and paths, the basic tree notions.8Union-Find (DSU)Each DSU group is a tree, and find walks up to its root.+Segment TreeA segment tree is a binary tree in which every node covers a range.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01What a tree is

A tree is a data structure for hierarchical data or processes: folders inside folders, managers above employees, moves in a game that lead to further moves.

The lecture defines it recursively. A tree T is either empty, or it consists of:

a special vertex r, the root,
zero or more subtrees T1, T2, …, Tk, each of which is itself a tree.

Each vertex (a node) stores a record: a value, a key or a state. The recursive shape is the part to remember. Whatever you want to do to a whole tree, you can usually do by handling the root and then calling the same function on each subtree. Almost every tree algorithm in this course is written exactly that way.

Every subtree is a tree in its own right: the definition calls itself.

02A tree is a graph without cycles

Forget the root for a moment and a tree is just a graph: a connected, undirected, acyclic graph. Connected means you can walk from any vertex to any other; acyclic means you can never walk in a circle.

For an undirected graph G = (V, E) the following statements are equivalent, so proving one gives you all the others:

G is a tree;
any two vertices are joined by exactly one simple path;
G is connected, but removing any edge disconnects it;
G is connected and E = V − 1;
G has no cycles and E = V − 1 (the slide lists only “no cycles”, but a forest of several separate trees has no cycles either);
G has no cycles, but adding any edge creates one.

The lecture’s tree has 10 vertices and 9 edges. Add one more, like the dashed 2–8, and a cycle appears at once.

The lecture’s tree: 10 vertices, 9 edges. The dashed edge 2–8 would close the red cycle.

03The root and the vocabulary

Often one vertex stands above the others: the root. You can “hang” the same tree from any vertex; the figure hangs the lecture’s tree from 5. Then:

every vertex except the root has exactly one parent, and 0, 1 or many children (9 is the parent of 3, 10, 6 and 7);
a leaf has no children; children of the same parent are siblings;
a path is a sequence of edges and its length is the number of edges (from 8 to 2 it is 5);
the depth of a vertex is the length of the path from the root to it;
the height of a vertex is the longest path from it down to a leaf, so every leaf has height 0;
tree height = height of the root = depth of the deepest leaf, here 4;
if n1 lies on the path from the root to n2, then n1 is an ancestor of n2 and n2 is a descendant of n1.

The same tree, hung from vertex 5.

04Binary trees and how to store them

In a binary tree every vertex has 0, 1 or 2 children, left(x) and right(x), and usually knows its parent(x) too. In C++ that is a struct with three pointers: struct node { int data; node *parent, *left, *right; };. The lecture also shows the table version: arrays parent[], left[], right[], where 0 means “no vertex”.

A full binary tree has 0 or 2 children at every vertex and all leaves at the same depth. Count the levels: 1, 2, 4, 8… so a full tree of height d holds 2^(d+1) − 1 vertices. Read it backwards: N vertices fit into height O(log N). That single fact is why balanced trees and heaps are fast.

If a vertex may have any number of children, store a vector of child pointers, or use the left-child, right-sibling trick: two pointers per node, exactly like a binary tree.

The full binary tree of the lecture: levels of 1, 2, 4 and 8 vertices.

05Three ways to visit every node

To traverse a tree means to visit every node exactly once. The lecture gives three recursive orders for a binary tree, and they differ only in when the parent is visited:

PREORDER: parent, left, right → 4, 7, 6, 1, 2, 8, 3, 9, 5
INORDER: left, parent, right → 6, 7, 2, 1, 4, 3, 9, 8, 5
POSTORDER: left, right, parent → 6, 2, 1, 7, 9, 3, 5, 8, 4

In code it is one function with the visit line moved: before the two recursive calls, between them, or after them. Each node is visited once, so every traversal costs O(n).

Each order has its job. Preorder copies a tree or prints it like nested folders. Inorder lists a binary search tree in sorted order (next lesson). Postorder handles the children before the parent: freeing memory, or evaluating an expression tree such as 16 + (7 + 5·4) / 9 − 2·3, where operators sit in the inner vertices and numbers in the leaves.

The tree of the lecture’s traversal slide. The root 4 comes first, in the middle, or last.

The lecture's C++C++

Slide 9: in memory every node stores its data and three pointers, one to its parent and one to each child.

struct node {
    int data;
    struct node *parent;
    struct node *leftchild;
    struct node *rightchild;
};

Cost at a glance

Any traversalO(n)

Edges in a treeV − 1

Height of a full binary treeO(log N)

Vertices of a full tree of height d2^(d+1) − 1

Remember

A tree is a connected graph without cycles, so it has exactly V − 1 edges and one path between any two vertices.
Depth is measured from the root down, height from a vertex down to its deepest leaf; the height of the tree is the height of its root.
Preorder, inorder and postorder are one recursive function; only the moment the parent is visited changes.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

More from the lectures▶ Trees, part 2

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the output strip: the same nine nodes come out in three different orders. Notice where the root 4 lands each time.

Interactive visualizerfocus here, then space ← →

Binary tree: PREORDER

Output sequence

(empty so far)

PREORDER (root → left → right): the parent is announced before its children. Used for copying trees and prefix notation.

Pseudocode

 1 preorder(v):  visit v; preorder(v.left); preorder(v.right) 2 inorder(v):   inorder(v.left); visit v; inorder(v.right) 3 postorder(v): postorder(v.left); postorder(v.right); visit v 4 // each node is visited exactly once → O(n)

1 / 1

Check

Three questions. Pick an answer to see why.

A connected undirected graph has 12 vertices and 12 edges. What can you be sure of?

You must free every node of a tree, and a node may be freed only after both of its children. Which traversal do you use?

A full binary tree has height 4. How many vertices does it have?

Practice

Real problems to lock it in, easiest first.

LeetCodeBinary Tree Inorder Traversal beginner↗LeetCodeMaximum Depth of Binary Tree beginner↗CSESSubordinates intermediate↗LeetCodeConstruct Binary Tree from Preorder and Inorder Traversal intermediate↗