Return the values of a binary tree in pre-order depth-first order: the current node, then everything in the left subtree, then everything in the right subtree.
depthFirstValues(root)
Input format: level-order with x for missing children. Output the values
space-separated.
3 9 20 x x 15 7 // → 3 9 20 15 7
1 2 3 // → 1 2 3
(empty) // → (empty)
"Depth-first" means committing to explore as far down one branch as possible before backing up to try the next — the opposite of sweeping across the tree level by level. Pre-order specifically means: record the current node's value first, then everything below it, left side entirely before right.
Ask the same local question every tree traversal starts with: what does a node need to produce its own contribution? Here the answer is an ordered list, and order matters. For pre-order: the node's own value first, then whatever the left subtree produces, then whatever the right subtree produces.
That's a direct recursive definition: an empty tree produces an empty list. A non-empty tree produces [this node's value] followed by the left subtree's list, followed by the right subtree's list.
The three pieces — node value, left results, right results — can be arranged differently: value first is pre-order, value in the middle is in-order, value last is post-order. All three use the identical recursive structure; only the placement of the current node's value changes. Once you understand one, you understand all three.
Since you fully finish the left subtree's entire recursive call before you even start the right subtree's, the left subtree's values are guaranteed to appear before any right subtree values, no matter how deep or lopsided the tree is. You don't manage this ordering yourself — it falls out of calls completing in sequence.
You could use an explicit stack instead of recursion (push right child, then left, then pop-and-record), producing the same pre-order sequence without the call stack. Good to know it exists, but the recursive version is simpler to reason about.
Every node is visited once and contributes exactly one value, so the work is proportional to the number of nodes.
def depth_first_values(root):
if root is None:
return []
return [root.val] + depth_first_values(root.left) + depth_first_values(root.right)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.