They are four ways to visit every node of a tree in a defined order. The first three are depth-first and differ only by when you handle the current node relative to its children.
Pre-order visits the node, then the left subtree, then the right. It suits copying a tree or writing a prefix expression.
In-order visits left, node, right, which yields sorted values on a binary search tree.
Post-order visits left, right, then the node. It suits deleting a tree or evaluating results bottom-up.
Level-order is the breadth-first one, visiting nodes row by row from the top with a queue. It suits questions about distance from the root.
All four touch every node once, so each costs O(n). The choice is about order, not speed.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
4It is 1st pre-order, 4th in-order, 7th post-order.
2It is 2nd pre-order, 2nd in-order, 3rd post-order.
1It is 3rd pre-order, 1st in-order, 1st post-order.
3It is 4th pre-order, 3rd in-order, 2nd post-order.
6It is 5th pre-order, 6th in-order, 6th post-order.
5It is 6th pre-order, 5th in-order, 4th post-order.
7It is 7th pre-order, 7th in-order, 5th post-order.
1step
At the top: 4 (It is 1st pre-order, 4th in-order, 7th post-order).
1 / 3← → keys
Pre-order visits the root first, in-order in the middle and post-order last. Level-order goes one depth at a time: the root 4, then 2 and 6, then 1, 3, 5 and 7.
How would you write in-order traversal iteratively, without recursion?Keep an explicit stack. Push the left chain, pop and visit a node, then go to its right child and repeat. Still O(n) time, O(h) extra space.
These are four orders for visiting every node in a tree, and three of them are depth-first while level-order is breadth-first.
The depth-first ones differ only in when you handle the current node: pre-order is node, left, right, in-order is left, node, right, and post-order is left, right, node.
Pre-order fits copying a tree or writing a prefix expression, and in-order on a binary search tree gives you the values in sorted order.
Post-order fits deleting a tree or computing results bottom-up, because you handle each node only after its children.
Level-order goes row by row from the root using a queue, which is what you want for questions about distance from the root.
All four visit each node once, so they're all O(n), and you pick one for the order the problem needs, not for speed.
Weak answers to avoid
Recites the orders with no use caseSaying node-left-right is memorization. Say what each one is for. In-order gives sorted BST output, post-order suits deletion, level-order suits distance from the root.
Says in-order always gives sorted outputThat holds only for a binary search tree. On an ordinary binary tree, in-order is just left, node, right, with no promise about value order.
Uses a stack for level-orderA stack gives depth-first order. Level-order needs a queue, so nodes leave in the order they were found and each row finishes before the next.
Claims one traversal is faster than anotherAll four touch every node once, so each is O(n) time. Pick by the order the problem needs. Only extra memory differs, path height for DFS and row width for BFS.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
