DSA problem
Binary Tree Preorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes' values. Preorder visits each node in the order root → left subtree → right subtree, so the very first value emitted is always the root, followed recursively by the entire left subtree, then the entire right subtree.
Preorder is the natural traversal whenever you want to process a node before descending into its children. It mirrors how you would copy a tree (you must clone the node first so the children have somewhere to attach), how you would serialize a tree to a string, and how prefix-expression evaluators read operators before their operands. Understanding the iterative form of this traversal is foundational for many tougher tree problems.
The recursive solution is a textbook three-liner: visit the current node, recurse left, then recurse right. It is clean and obvious, but it consumes O(h) call-stack frames where h is the tree's height, which can be O(n) in the worst case for a skewed tree.
The iterative solution swaps the implicit call stack for an explicit one. Push the root onto the stack, then in a loop pop a node, record its value, and push its right child first followed by its left child — pushing right first ensures left is popped (and therefore visited) first, preserving the root-left-right order. Both forms run in O(n) time; the iterative form makes the data flow visible and is the canonical implementation you should be ready to write under interview pressure.
Examples
root = [1,null,2,3][1,2,3]root = [][]root = [1,2,3,4,5,null,6][1,2,4,5,3,6]Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
- The tree is a valid binary tree (each node has at most two children).
- Follow-up: an iterative O(n)-time, O(h)-space solution is expected.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.