Root-First Visit Order
EasyTreesFree
Problem
A file-system indexer prints a directory tree by announcing each folder before anything inside it, then exploring its left branch completely, then its right branch.
Given the root of a binary tree, return the node values in that order (a preorder traversal). Solve it without recursion.
Example 1
- Input:
- root = [1, null, 2, 3]
- Output:
- [1, 2, 3]
Visit 1, it has no left child, go right to 2, then 2's left child 3.
Example 2
- Input:
- root = [4, 2, 6, 1, 3, 5, 7]
- Output:
- [4, 2, 1, 3, 6, 5, 7]
Example 3
- Input:
- root = []
- Output:
- []
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
Recursion keeps the 'what to visit next' list on the call stack. Can you keep it on an explicit stack instead?
Walkthrough
How to approach it
01Clarify before coding
- Is the empty tree valid? Yes: return an empty list.
- Why no recursion? A skewed tree of 10^4 nodes would recurse 10^4 deep, beyond Python's default limit; an explicit stack has no such ceiling.
- Do values need to be unique? No, we only report them in order.
02Brute force
The textbook recursive version: record the node, recurse left, recurse right.
Cost: O(n) time and O(h) stack, which is correct but crashes on a 10^4-deep chain in Python. The question asks us to remove that risk.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.