Tree Traversal: Why the Order You Pick Is a Data Flow Decision
Tree traversal usually gets taught as three separate algorithms to memorize: preorder, inorder, postorder. They are not three algorithms. They are one recursive function with a single line moved to a different spot, and that one line decides which problems you can solve. I watched this trip up people prepping for months. They had all four traces memorized and still froze when a new problem asked them to pick an order. The trace is the easy part. Knowing which order hands you the information you need is the part that actually matters in an interview. TL;DR: Traversal visits every node once. The four standard orders differ only in when the current node gets processed relative to its children. Preorder processes the node before its children, postorder after, inorder between, and level order goes breadth first with a queue. Pick the order by asking which direction data has to move between a parent and its children. Run all four on the same tree and the difference stops being abstract. 1 / \ 2 3 / \ \ 4 5 6 / 7 Preorder (node, left, right): 1, 2, 4, 7, 5, 3, 6 Inorder (left, node, right): 7, 4, 2, 5, 1, 3, 6 Postorder (left, right, node): 7, 4, 5, 2, 6, 3, 1 Level order (breadth first): 1, 2, 3, 4, 5, 6, 7 Inorder looks unsorted here because this is not a binary search tree. The sorted property only shows up when the values obey the BST invariant of left less than node less than right. On a plain binary tree, inorder still walks left, node, right, but the numbers come out in whatever order the structure gives you. The three depth first orders are the same code. The recursive call structure is identical. The only difference is where the line that processes the node sits relative to the two recursive calls. def preorder(node): if not node: return process(node) # before the children preorder(node.left) preorder(node.right) def inorder(node): if not node: return inorder(node.left) process(node) # between the children inorder(node.right) def postorder(node): if not node: retu
