Binary Tree Preorder Traversal
EasyPrompt
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation:
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]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Approaches
3 approaches with complexity analysis and trade-offs.
The most intuitive way to perform a preorder traversal is using recursion. The preorder traversal follows the order: Root -> Left -> Right. A recursive function can naturally implement this by processing the current node, then making a recursive call for the left child, followed by a recursive call for the right child.
Algorithm
- Create a helper function, say
traverse(node, resultList). - If the current
nodeisnull, return. - Add the
node.valto theresultList(visiting the root). - Recursively call
traverse(node.left, resultList)to traverse the left subtree. - Recursively call
traverse(node.right, resultList)to traverse the right subtree.
Walkthrough
This approach uses a helper function that takes the current node and a list to store the results. The base case for the recursion is when the node is null. Otherwise, it first adds the current node's value to the list, then makes a recursive call on the left child, and finally on the right child. This order of operations perfectly matches the definition of preorder traversal.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); traverse(root, result); return result; } private void traverse(TreeNode node, List<Integer> result) { if (node == null) { return; } result.add(node.val); // Visit the root traverse(node.left, result); // Traverse left subtree traverse(node.right, result); // Traverse right subtree }}Complexity
Time
O(N), as each node is visited exactly once.
Space
O(H), where H is the height of the tree. In the worst case of a skewed tree, this is O(N).
Trade-offs
Pros
Simple and intuitive to understand and implement.
The code directly reflects the definition of preorder traversal.
Cons
Can lead to a
StackOverflowErrorfor very deep or skewed trees due to the depth of recursion.The space complexity is dependent on the height of the tree, which can be O(N) in the worst case.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > preorderTraversal ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); while ( root != null ) { if ( root . left == null ) { ans . add ( root . val ); root = root . right ; } else { TreeNode prev = root . left ; while ( prev . right != null && prev . right != root ) { prev = prev . right ; } if ( prev . right == null ) { ans . add ( root . val ); prev . right = root ; root = root . left ; } else { prev . right = null ; root = root . right ; } } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.