Tree Traversals (Inorder, Preorder, Postorder)

Given the root of a binary tree, return the **inorder**, **preorder**, and **postorder** traversals as three separate arrays.

- **Preorder**: Root → Left → Right

- **Inorder**: Left → Root → Right

- **Postorder**: Left → Right → Root

Input: root = [1, null, 2, 3]

Output: { inorder: [1,3,2], preorder: [1,2,3], postorder: [3,2,1] }

For a tree with root 1, right child 2, and 2's left child 3.

Input: root = [1]

Output: { inorder: [1], preorder: [1], postorder: [1] }

Single node tree.

Time

O(n)

each node is visited exactly once per traversal.

Space

O(h)

recursion stack depth equals tree height h; O(n) worst-case for skewed trees.

#1 Basic tree

Input: [1, null, 2, 3]

Expected: {"inorder":[1,3,2],"preorder":[1,2,3],"postorder":[3,2,1]}

#2 Empty tree

Input: []

Expected: {"inorder":[],"preorder":[],"postorder":[]}

#3 Single node

Input: [1]

Expected: {"inorder":[1],"preorder":[1],"postorder":[1]}

#4 Full tree

Input: [1,2,3,4,5]

Expected: {"inorder":[4,2,5,1,3],"preorder":[1,2,4,5,3],"postorder":[4,5,2,3,1]}