Trees

Trees are a broad type of data structure. A fairly common variant is the binary tree. Quick links:

• LeetCode problem list

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 the maximum length from the root of the tree to any node in the tree, plus one (think about this intuitively).
• A set of nodes $S:\{n_0,n_1,\dots ,n_{k-1},n_k\}$ is a path from nodes $n_0$ to $n_k$ if node $n_i$ is the parent of node $n_{i+1}$ for $i\in [0,k]$.
• The path from $n_0$ to $n_k$ has a length of $k$, 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 $d$ before searching nodes at $d+1$.

Types

• Binary tree
  • Binary search tree
    • AVL tree
    • Red-black tree
• Prefix tree
• Algorithms
  • Breadth-first search
  • Depth-first search

Applications

• Document Object Model
• UNIX filesystem