Trees - 401-advanced-javascript-billybunn/seattle-javascript-401d29 GitHub Wiki
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:
- Preorder
- Inorder
- 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.