Home [Data Structure] BFS, DFS
Post
Cancel

[Data Structure] BFS, DFS

BFS

  • Graph의 경우 queue (deque)으로 구현
  • Matrix의 경우 recursive로 구현
  • level order (BFS, using queue)
  • time complexity: O(n)
  • space complexity: best: O(1), worst: O(n/2) = O(n)

DFS

  • Graph의 경우 stack으로 구현
  • Matrix의 경우 recursive로 구현
  • time complexity: O(n)
  • space complexity: best: O(log n) - avg.height of tree worst: O(n)
  • self가 기준
    • inorder: left, self, right
    • postorder: left, right, self
    • preorder: self, left, right
This post is licensed under CC BY 4.0 by the author.

Amazon onsite interview plan

[Algorithm] Longest substring without repeating charaters