What is the difference between depth-first search and breadth-first search on trees?

Depth-first search, or DFS, explores as deep as possible along each branch before backtracking. It uses recursion or an explicit stack and processes nodes in preorder, inorder, or postorder sequences. DFS uses O of h space where h is the tree height. Breadth-first search, or BFS, explores all nodes at the current level before moving to the next level. It uses a queue and processes nodes level by level. BFS uses O of w space where w is the maximum width. Use DFS when the answer involves paths from root to leaf or when you need to explore all possibilities.