Given the root of a binary tree, return the values of its nodes in preorder: first the node itself, then its left subtree, then its right subtree.
Example 1
Input: root = [1,null,2,3]
Output: [1,2,3]
Example 2
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Constraints
- The number of nodes is in the range 0 to 100
- -100 <= Node.val <= 100
Hints
Frequently asked at: Amazon, Microsoft, Accenture, Cognizant
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Recursion solves it directly in O(n), and the interview question is usually "now do it iteratively". In preorder a node is recorded the moment we reach it, so a stack works very simply: pop, record, and push the children. Because a stack is last in first out, pushing the right child first means the left subtree is fully processed before the right one, which is exactly preorder.
Algorithm
- If
rootis null, return[]. Otherwise pushrooton a stack. - While the stack is not empty, pop a node and append its value.
- Push its right child (if any), then its left child (if any).
Time:
O(n)Space: O(h) for the stack in the typical case, O(n) worst caseInterview tip: Mixing up the push order (left before right) gives a "root, right, left" order. Reversing that list is actually a quick way to get postorder, a popular follow-up.
class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res, stack = [], [root] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) # right first... if node.left: stack.append(node.left) # ...so left is popped first return resCtrl + Enter runs the examples