144. Binary Tree Preorder Traversal
You receive root, the top node of a binary tree (possibly null for an empty tree). Each node has an integer val plus left and right child pointers. Return the tree's preorder traversal as a list of values: record the node itself first, then everything in its left subtree, then everything in its right subtree.
For input purposes the tree is written in level order with the word null marking a missing child — for example 1 2 3 null 4 is a root 1 whose left child 2 has only a right child 4, and whose right child is 3.
Recursion makes this a three-liner. The exercise worth doing is the iterative version: drive the traversal yourself with an explicit stack.
Example 1:
Input: root = [1, null, 2, 3]
Output: [1, 2, 3]
Explanation: Root 1 has no left child, so after recording 1 we descend right to 2, then into 2's left child 3.
Example 2:
Input: root = [1, 2, 3, 4, 5, null, 6]
Output: [1, 2, 4, 5, 3, 6]
Explanation: Record 1, then the whole left subtree (2, then its children 4 and 5), then the right subtree (3, then its right child 6).
Constraints:
- 0 ≤ number of nodes ≤ 100
- -100 ≤ Node.val ≤ 100
Hints:
Preorder is literally its own definition: handle the node, recurse into the left child, recurse into the right child. Write that, confirm it works — then try again with recursion banned.
For the iterative version, a stack replaces the call stack: pop a node, record its value, and push its right child before its left child, so the left child is processed first.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, null, 2, 3]
Expected output: [1, 2, 3]