This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬
Tree Definition & Representation
Knowledge Summary
Basic Concepts of Trees
- Tree: a finite set of n nodes; when n = 0, it is an empty tree
- Root node: a node with no parent
- Leaf node: a node with no children
- Internal node: a node that has both a parent and children
- Depth: the length of the path from the root to the node (the root's depth may be defined as 0 or 1 depending on the problem)
- Height: the length of the path from the node to its deepest leaf
- Degree: the number of children of a node
Important Properties of Trees
- A tree with n nodes has n-1 edges
- There is exactly one path between any two nodes in a tree
- In a tree of degree m, the i-th level can have at most m^(i-1) nodes (with the root at level 1)
Ways to Store Trees
- Parent representation: each node records the index of its parent
- Children representation: each node stores a list of its children
- Left-child right-sibling representation: converts a general tree into a binary tree
Forest
A collection of multiple disjoint trees is called a forest.
- A forest can be converted into a binary tree using the left-child right-sibling method
- A binary tree can also be converted back into a forest