• [ ] AVL tree, red-black tree, B tree
• [ ] Deque isEmpty

The iterative version (stack + pointer) is quite hard and unintuitive. Esp the post-order traversal which requires one more pointer.

Concept recap

• Full binary tree: either 0 or 2 children

• Complete binary tree: all but the last level have 2 children (max number of nodes); the last level filled from left to right

• traversal

  • depth first
    • pre-order
    • in-order
    • post-order
  • breath first
    • level order

• storage

  • chain storage
  • sequential storage

Recursive traversal

1. Identify the parameter(s) and return value (type) of the recursive function
2. Identify the stop condition of the recursion
   • remember to CHECK FOR NULL in the recursive function
3. Find the what need to be processed for each layer of recursion

Iterative traversal (version 1, plain)

• “visit” and “process (e.g. print)” are done at the same time
• only works for pre-order; can work on post-order by “self - right - left” and reverse output list