Trees

Trees are similar to linked lists, in that they contain nodes that reference another node; but with trees (binary trees in particular), each node references two other nodes: a left and a right.

Traversal

When we traverse a tree, there are two approaches: depth first and breadth first.

• Depth first traversals are what they sound like; we travel first down the height of the tree. Usually, depth first traversals are done with recursion. A depth first traversal can look at each root in three different orders:

  1. Preorder
  2. Inorder
  3. Postorder

• Breadth first traversals look through each level of the tree (horizontally). A queue is the way we'd look throw the width of the tree level-by-level.

Reading

• Trees