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.
To avoid the limitations of recursion, we can implement the preorder traversal iteratively using an explicit stack. This approach mimics the behavior of the recursion call stack. We process a node, then push its children onto the stack to be processed later. Since a stack is a Last-In-First-Out (LIFO) data structure, we push the right child first, then the left child, to ensure the left subtree is processed before the right subtree.
Algorithm
- Initialize an empty list
result. - If the
rootisnull, return the empty list. - Create an empty
Stackand push therootnode onto it. - While the stack is not empty:
- Pop a node from the stack.
- Add the node's value to the
resultlist. - Push the right child onto the stack if it exists.
- Push the left child onto the stack if it exists. (Note: Push right child first so left is processed first).
- Return the
resultlist.
Walkthrough
This method replaces the implicit function call stack of recursion with an explicit Stack data structure. We start by pushing the root node. In each iteration of the loop, we pop a node, add its value to our result list, and then push its children onto the stack. Crucially, the right child is pushed before the left child. This ensures that the left child, being on top of the stack, is popped and processed next, correctly following the preorder (Root, Left, Right) sequence.
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // Push right child first so that left child is processed first if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return result; }}Complexity
Time
O(N), as each node is pushed and popped from the stack 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
Avoids recursion depth limits and the potential for stack overflow.
Can handle very deep trees that would fail with a recursive approach.
Cons
Requires extra space for the stack, which can be up to O(N) for a skewed tree.
Morris Traversal is an advanced, highly space-efficient technique that performs a traversal in O(1) auxiliary space. It achieves this by temporarily modifying the tree's structure. It creates temporary links (threads) from the inorder predecessor of a node back to the node itself, allowing traversal back up the tree without a stack or recursion. After the subtree is visited, these links are removed to restore the original tree structure.
Algorithm
- Initialize an empty list
resultand setcurrentpointer toroot. - While
currentis notnull:- If
currenthas no left child, add its value toresultand movecurrentto its right child. - If
currenthas a left child, find its inorder predecessor (the rightmost node in the left subtree).- If the predecessor's right child is
null: Addcurrent.valtoresult, create a temporary link from the predecessor's right child tocurrent, and movecurrentto its left child. - If the predecessor's right child is
current: Break the temporary link and movecurrentto its right child.
- If the predecessor's right child is
- If
- Return
result.
Walkthrough
The core idea is to traverse the tree without recursion or a stack. When at a current node, we check if it has a left child. If not, we visit it and move right. If it does, we find its inorder predecessor. We then use the predecessor's right pointer (which is normally null) to create a temporary link back to the current node. For preorder, we visit the current node's value before traversing the left subtree (i.e., when we create the link). After the left subtree is fully traversed, we revisit the current node via this link, at which point we remove the link and move to the right subtree.
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); TreeNode current = root; while (current != null) { if (current.left == null) { result.add(current.val); current = current.right; } else { // Find the inorder predecessor of current TreeNode predecessor = current.left; while (predecessor.right != null && predecessor.right != current) { predecessor = predecessor.right; } if (predecessor.right == null) { // This is the first time we visit this node. // Visit the node, create the thread, and move to the left. result.add(current.val); predecessor.right = current; current = current.left; } else { // The thread already exists. We have visited the left subtree. // Remove the thread and move to the right. predecessor.right = null; current = current.right; } } } return result; }}Complexity
Time
O(N). Although there's a nested loop, each edge is traversed at most twice, leading to an amortized linear time complexity.
Space
O(1), as no extra space proportional to the input size is used besides the output list.
Trade-offs
Pros
Extremely space-efficient with O(1) auxiliary space (excluding the output list).
Does not use recursion or an explicit stack, making it very robust.
Cons
The algorithm is complex and harder to understand and implement correctly.
It temporarily modifies the input tree, which might not be permissible in all scenarios (though it does restore the tree's original structure).
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 ; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < int > preorderTraversal ( TreeNode * root ) { vector < int > ans ; while ( root ) { if ( ! root -> left ) { ans . push_back ( root -> val ); root = root -> right ; } else { TreeNode * prev = root -> left ; while ( prev -> right && prev -> right != root ) { prev = prev -> right ; } if ( ! prev -> right ) { ans . push_back ( root -> val ); prev -> right = root ; root = root -> left ; } else { prev -> right = nullptr ; root = root -> right ; } } } return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def preorderTraversal ( self , root : Optional [ TreeNode ]) -> List [ int ]: ans = [] while root : if root . left is None : ans . append ( root . val ) root = root . right else : prev = root . left while prev . right and prev . right != root : prev = prev . right if prev . right is None : ans . append ( root . val ) prev . right = root root = root . left else : prev . right = None root = root . right return ansVideo 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.