A strong answer
All three are depth-first: they recurse into the left subtree and then the right subtree. They differ in when the node itself is processed.
- Preorder (node, left, right) processes a parent before its children. I use it when children need something from the parent, or to record a tree's structure top-down: copying or serializing a tree, printing an indented folder listing, prefix notation.
- Inorder (left, node, right) is mostly useful for binary search trees, where it visits keys in sorted order: listing a sorted set, finding the kth smallest key, validating a BST.
- Postorder (left, right, node) processes a node after both children. I use it when a node depends on its children's results: computing heights or folder sizes, evaluating an expression tree (it produces postfix notation), and freeing memory, where children must be freed before the parent's pointers to them disappear.
Each visits every node once: O(n) time. The recursion uses O(h) stack space for height h, which is O(log n) for a balanced tree and O(n) for a degenerate chain, where deep recursion can overflow the stack. Iterative versions use an explicit stack: preorder pushes right then left children; inorder pushes nodes while going left, then pops and turns right; postorder needs to remember whether a node's children have been handled.
Breadth-first (level-order) traversal is the alternative: it uses a queue and visits nodes by depth.
What the interviewer is listening for
- The three definitions, stated precisely.
- A convincing use case for each, especially postorder for deletion and evaluation.
- Complexity, including stack depth, and how to traverse iteratively.
Common mistakes
- Saying inorder gives sorted output for any binary tree, not just a BST.
- Freeing nodes in preorder.
- Claiming O(1) space for the recursive versions.