Sunday, 3 June 2018

data structure

1. tree
  • 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