Traversal

• BFS(breadth-first search) and DFS(depth-first search) - Youtube (video)
  • BFS notes:
    • BFS - MIT 6.006 (video)
    • level order (BFS, using queue)
    • time complexity: O(n)
    • space complexity: best: O(1), worst: O(n/2)=O(n)
  • DFS notes:
    • DFS - MIT 6.006 (video)
    • time complexity: O(n)
    • space complexity: best: O(log n) - avg. height of tree worst: O(n)
    • inorder (DFS: left, self, right)
    • postorder (DFS: left, right, self)
    • preorder (DFS: self, left, right)