Left-Root-Right Reading
EasyTreesFree
Problem
A layout engine flattens a binary tree of widgets into a single row: every widget is placed after all widgets of its left branch and before all widgets of its right branch.
Given the root of a binary tree, return the values in that order (an inorder traversal). Use an explicit stack rather than recursion.
Example 1
- Input:
- root = [1, null, 2, 3]
- Output:
- [1, 3, 2]
1 has no left branch, so it comes first; 2's left child 3 must precede 2.
Example 2
- Input:
- root = [4, 2, 6, 1, 3, 5, 7]
- Output:
- [1, 2, 3, 4, 5, 6, 7]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -1000 ≤ node.val ≤ 1000
Hint
Show the first hint
Before you can output a node you must finish its entire left branch. Where do you park the node meanwhile?
Walkthrough
How to approach it
01Clarify before coding
- Is the tree a search tree? Not necessarily; we only report positions, not sorted values.
- Can it be empty? Yes: return [].
- Deep trees? Up to 10^4 nodes in a line, which is why recursion is ruled out.
02Brute force
Recursive inorder: recurse left, record the node, recurse right.
Cost: O(n) time, O(h) call stack: correct, but a 10^4-deep chain overflows Python's recursion limit.
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.