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

Applications