Binary Tree Preorder Traversal
Easy · Trees · Stack · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, return the preorder traversal of its values: visit a node, then its entire left subtree, then its entire right subtree.
The recursive version is three lines. As a follow-up, produce the same order iteratively with an explicit stack, and then with no stack at all.
Examples
Input: root = [6,2,8,1,4] Output: [6,2,1,4,8]
Root 6 first, then the left subtree 2, 1, 4, then the right node 8.
Input: root = [3,null,5,7] Output: [3,5,7]
3 has only a right child 5, whose left child is 7.
Input: root = [] Output: []
An empty tree has no values.
Constraints
- the tree has between 0 and 100 nodes
- -100 <= Node.val <= 100
Approaches
- Concatenate the subtrees' lists — time O(n · h), O(n²) for a chain, space O(n · h) of temporary lists
Follow-up
Inorder and postorder fit the same frameworks. With a stack, inorder walks left as far as possible before visiting; postorder is preorder with the children swapped (node, right, left), reversed. With Morris, inorder records on the second visit instead of the first.
Related problems
Start free on Cariara · Coding problems · System design studio
