Preorder, Inorder & Postorder Traversal

The problem. Given the root of a binary tree, return the values of its nodes in preorder, inorder and postorder. (On LeetCode these are three separate questions — 144, 94 and 145 — but they are one idea, so they share one lesson.)

Example

root = [1, 2, 3, 4, 5, null, 6]
preorder  -> [1, 2, 4, 5, 3, 6]
inorder   -> [4, 2, 5, 1, 3, 6]
postorder -> [4, 5, 2, 6, 3, 1]

All three are depth-first: go all the way down the left side before the right side. The only difference is when you write down the node — the name says where the root goes: pre = before its subtrees, in = in between them, post = after them.

Each order has a job. Preorder copies or serializes a tree (you meet the root first, so you can rebuild it). Inorder of a binary search tree gives the values in sorted order. Postorder handles children before parents — deleting a tree, or computing sizes and heights.