List a Tree's Values Node, Left, Right
Solve this ProblemYou are given the root of a binary tree. Return the values of all its nodes in the order you meet them when, at every node, you take the node itself first, then walk its entire left subtree, then its entire right subtree.
A recursive helper does this directly. The same order can also be produced iteratively with a stack that holds the nodes still waiting to be taken.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Take every node before either of its subtrees: the node itself, then its whole left subtree, then its whole right subtree. Return the values in the order taken
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Walk
GoodA helper takes a node, records its value straight away, then walks the whole left subtree, then the whole right subtree. A missing child returns immediately. Each node is entered once (O(n) time); the recursion goes as deep as the tree is tall, so the extra space is O(h) — up to O(n) when the tree is one long chain.
O(n)O(h)1class Solution {
2 public List<Integer> preorderValues(TreeNode root) {
3 List<Integer> out = new ArrayList<>();
4 walk(root, out);
5 return out;
6 }
7
8 private void walk(TreeNode node, List<Integer> out) {
9 if (node == null) return;
10 out.add(node.val);
11 walk(node.left, out);
12 walk(node.right, out);
13 }
14}Optimal — Iterative Walk With an Explicit Stack
OptimalKeep your own stack of nodes still to be taken. Start with the root on it. Repeat: pop a node, record it, then push its right child and then its left child (each only if it exists). Because the stack hands back the most recent push first, the left child comes out before the right one — and the whole left subtree is finished before the right child is touched. Every node is pushed and popped once, so the time is O(n) and the stack holds at most about one path of pending right children (O(h)); there is no deep call chain to overflow.
O(n)O(h)1class Solution {
2 public List<Integer> preorderValues(TreeNode root) {
3 List<Integer> out = new ArrayList<>();
4 if (root == null) return out;
5 Deque<TreeNode> stack = new ArrayDeque<>();
6 stack.push(root);
7 while (!stack.isEmpty()) {
8 TreeNode node = stack.pop();
9 out.add(node.val);
10 if (node.right != null) stack.push(node.right);
11 if (node.left != null) stack.push(node.left);
12 }
13 return out;
14 }
15}