- pre-order: root node pre child
- post-order: root node post child
- in-order: root node inbetween child
- always use stack to iterate
2. pre-order
- push root, pop root
- push right child, push left child
- top of stack become new root
- go back
3. post-order
- push root
- push left child
- top of stack become new root
- if no left child, pop
- right child become new root
4. binary search tree (balanced)
- if not balanced, bst may end up as linked list
- avl tree and red-black tree are bst
5. other type of tree
- heap (insert from left to right)
- priority queue (insert from left to right)
- trie (prefix tree that often store string)
reference
No comments:
Post a Comment