A strong answer
Both visit every node once, in O(n) time. They differ in order and in what they keep in memory.
DFS (preorder, inorder or postorder, with recursion or an explicit stack) finishes a whole subtree before moving to its sibling. It holds one root-to-leaf path at a time: O(h) memory, which is O(log n) for a balanced tree but O(n) for a chain. It fits problems where a node's answer comes from its subtrees (heights, sizes, path sums, validation) and anything that needs sorted BST order.
BFS (level order, with a queue) visits nodes in order of depth. It holds one level at a time, plus part of the next: for a complete tree the bottom level has about n/2 nodes, so O(n) memory, but a long thin tree needs only O(1). It fits problems about depth and levels: the minimum depth (it can stop at the first leaf instead of exploring deep branches), level averages, right-side views, zigzag order, and serialization in the common level-order format. Taking a snapshot of the queue's length at the start of each round separates the levels.
So I choose by the order the problem needs first: per-level or nearest-first questions favor BFS, subtree-combining questions favor DFS. Then I check memory: for a very deep tree, I avoid recursive DFS or switch to an explicit stack; for a very wide one, BFS's queue can be the larger cost.
What the interviewer is listening for
- The visiting order of each, and problems that need each order.
- Memory in terms of height and width, with both extreme tree shapes.
- The level-size snapshot technique.
Common mistakes
- Saying BFS always uses less memory, or always more.
- Using a list with pop(0) as the queue, which makes BFS quadratic.
- Forgetting the stack-overflow risk of recursive DFS on deep trees.