Binary Tree Preorder Traversal
Problem Description
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Output: [1,2,3]
Example 2:
Output: [1,2,4,5,6,7,3,8,9]
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?
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The recursive approach is the most straightforward way to perform a preorder traversal of a binary tree. In a preorder traversal, the root node is visited first, followed by the left subtree, and finally the right subtree. The recursive implementation mimics this order naturally by recursively calling the preorder function for each subtree.
Approach:
- Visit the root node first.
- Recursively traverse the left subtree.
- Recursively traverse the right subtree.
Code:
- Time Complexity: O(n), where n is the number of nodes in the binary tree, as we visit each node once.
- Space Complexity: O(n) in the worst case due to the recursion stack, and O(log n) for a balanced tree.
2. Iterative Approach using Stack
Intuition:
An iterative approach using a stack is a common way to avoid recursion and control the function call behavior explicitly. The idea is to mimic the system's call stack with an explicit stack data structure to store nodes yet to be processed.
Approach:
- Use a stack to keep track of nodes. Initially, push the root node to the stack.
- While the stack is not empty, pop a node from the stack, add its value to the result list, and then push its right and left children to the stack (in that order).
- This ensures that nodes are processed in preorder sequence.
Code:
- Time Complexity: O(n), since each node is processed (visited and added to the result list) once.
- Space Complexity: O(n), in the worst case, due to the stack holding all nodes (in the case of a skewed tree). In the best case of a balanced tree, it's O(log n).
3. Morris Traversal (Most Optimal)
Intuition:
Morris Traversal modifies the tree structure temporarily to allow traversal of the tree without using additional space or a stack. It uses the concept of threading a binary tree.
Approach:
- Start with the root node and initialize the
currentnode to root. - While the current node is not null:
- If the current node has no left child, add its value to the result and move to its right child.
- If the current node has a left child, find the rightmost node in the left subtree (inorder predecessor).
- If the rightmost node's right child is null, set its right child to the current node, and move to the left child.
- If the rightmost node's right child is the current node (thread already exists), set it back to null (restoring tree structure), add the current node's value to result, and move to its right child.
Code:
- Time Complexity: O(n), as each edge and node is visited at most twice (the second time goes without child links).
- Space Complexity: O(1), as no additional data structures or recursion stacks are used beyond the result list.