Trees are a broad type of data structure. A fairly common variant is the binary tree. Quick links:
Basics
What distinguish trees from other data structures? Like lists or graphs?
- They have nodes, with edges to connect the nodes.
- No cycles (self-explanatory).
- One parent, multiple children.
- One root (parent) node, unless it’s an empty tree (then it’d have zero roots).
Some definitions:
- The height of a tree is defined as the length of the longest path from any node to any leaf in the tree rooted at that node.
- A set of nodes is a path from nodes to if node is the parent of node for .
- The path from to has a length of , i.e., the number of edges, or one less than the number of nodes along the path.
Algorithms and traversal
Our basic traversal algorithms for trees involve pre-order and post-order traversal. The basic idea with pre-order traversal is that we visit the root of the tree first, then the sub-trees are traverse recursively. The opposite of this is post-order, where the subtrees down to the leaves are traversed first, then we work up to the roots.
Breadth-first search and depth-first search propose a different approach. BFS suggests we search all nodes at a given depth before searching nodes at .
Types
- Binary tree
- Prefix tree
- Algorithms