Binary Tree Inorder Traversal
Problem Description
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Example 2:
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:
In an inorder traversal, we visit the left subtree first, then the root, and finally the right subtree. The recursive approach is a direct and simple way to implement this traversal. We can use a recursive function to traverse the left subtree, visit the root node, and then traverse the right subtree.
Code:
- Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
- Space Complexity: O(n) in the worst case due to the system stack when the tree is skewed. In case of a balanced tree, it's O(log n).
2. Iterative Approach with Stack
Intuition:
Instead of using the system's call stack which the recursive approach does implicitly, we can use an explicit stack to simulate the traversal. This approach iteratively manages the nodes to be processed by continuously traversing the left while recording nodes on the stack. When it reaches a node without a left child, it pops from the stack and moves to the right subtree.
Code:
- Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed exactly once.
- Space Complexity: O(n) in the worst case (for a completely skewed tree) and O(log n) for a balanced tree.
3. Morris Traversal
Intuition:
Morris Traversal provides a way to perform the inorder traversal without extra space. The idea is to temporarily make a link from the rightmost node of left subtree to the root node, which allows us to traverse without a stack. After visiting, we have to restore the tree back to its original structure.
Code:
- Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node at most twice (once to create a thread and once to remove it).
- Space Complexity: O(1), as no extra space is used apart from variables.