Trees

Objectives

What is a recursive data sctructure? How is a tree recursive in nature?

Your answer...
On your desk, create a tree containing the following values (in any order): 4, 1, 8, 3, 2

How many steps does it take to find the value 3?

Your answer...
Given pseudocode write an algorithm to print every value in a tree:
```
  print root node value
  for each child of root node
    print node value
    for each child of child
      print node value
      ...
```
(This pseudocode is recursive... what is the base condition for this recursive algorithm?)

Code your solution here: https://repl.it/@galvanize/BasicTrees

Define what a binary search tree is
Explain when binary search trees are useful
Write pseudo code to traverse a binary search tree
Explain the difference between depth first search methods:
- Pre-order
- In-order
- Post-order
Describe the Big O of Binary Search Trees.
- Insert
- Remove
- Look up
- Traverse
Implement binary search tree methods:
- DFS
- BFS

What is a binary search tree? What are it's restrictions? When might they useful?

Your answer...
Diagram the following set of numbers as a binary search tree:
- 1, 3, 4
- 3, 1, 4
- 5, 3, 8, 4, 0, 6, 7
How do you traverse a binary tree? What are the 4 orders we can traverse a tree in? How do Pre-order, In-order and Post-order differ?

Your answer...
What is the Big-O of Binary Search Trees methods (average and worst cases):
- Insert
- Remove
- Lookup
- Traverse