Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Approach 1: Recursive Approach
class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
helper(root, res);
return res;
}
public void helper(TreeNode root, List res) {
if (root != null) {
helper(root.left, res);
res.add(root.val);
helper(root.right, res);
}
}
}
Time Complexity and Space Complexity is O(n).
Approach 2: Iterating method using Stack
public class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
}
Time Complexity and Space Complexity is O(n).
Approach 3: Morris Traversal
/*
For example:
1
/ \
2 3
/ \ /
4 5 6
First, 1 is the root, so initialize 1 as current, 1 has left child which is 2, the current's left subtree is
2
/ \
4 5
So in this subtree, the rightmost node is 5, then make the current(1) as the right child of 5. Set current = current.left (current = 2). The tree now looks like:
2
/ \
4 5
\
1
\
3
/
6
For current 2, which has left child 4, we can continue with the same process as we did above
4
\
2
\
5
\
1
\
3
/
6
then add 4 because it has no left child, then add 2, 5, 1, 3 one by one, for node 3 which has left child 6, do the same as above. Finally, the inorder traversal is [4,2,5,1,6,3].
*/
class Solution {
public List inorderTraversal(TreeNode root) {
List res = new ArrayList<>();
TreeNode curr = root;
TreeNode pre;
while (curr != null) {
if (curr.left == null) {
res.add(curr.val);
curr = curr.right; // move to next right node
} else { // has a left subtree
pre = curr.left;
while (pre.right != null) { // find rightmost
pre = pre.right;
}
pre.right = curr; // put cur after the pre node
TreeNode temp = curr; // store cur node
curr = curr.left; // move cur to the top of the new tree
temp.left = null; // original cur left be null, avoid infinite loops
}
}
return res;
}
}
Time Complexity is O(n) and Space Complexity is O(1).
See Video lecture
Leetcode 102. Binary Tree Level Order Traversal
Introduction
Binary Tree Inorder Traversal is a classic traversal technique used in tree data structures. The traversal follows the **Left-Root-Right** order, which means:
- Traverse the left subtree first.
- Visit the root node.
- Traverse the right subtree.
This traversal is especially significant because it produces nodes in ascending order if the binary tree is a binary search tree (BST).
Problem Statement
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example
Consider the binary tree:
1
\
2
/
3
The inorder traversal output is:
[1, 3, 2]
Approach
There are two common ways to implement inorder traversal:
- Using recursion.
- Using an iterative approach with a stack.
Recursive Solution
The recursive solution leverages the natural hierarchical structure of trees. The recursive function processes the left subtree, the root, and the right subtree in the correct order.
Steps to Solve
- Call the recursive function on the left subtree.
- Add the root node's value to the result.
- Call the recursive function on the right subtree.
Implementation
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List inorderTraversal(TreeNode root) {
List result = new ArrayList<>();
traverse(root, result);
return result;
}
private void traverse(TreeNode node, List result) {
if (node == null) {
return;
}
traverse(node.left, result); // Traverse left subtree
result.add(node.val); // Process root
traverse(node.right, result); // Traverse right subtree
}
}
Iterative Solution
The iterative solution uses a stack to simulate the call stack in recursion. It allows traversing the tree in the desired order without using recursion.
Steps to Solve
- Initialize an empty stack and a pointer
currentto the root. - Push all left nodes onto the stack until the leftmost node is reached.
- Pop a node from the stack, process it, and move to its right child.
- Repeat the process until the stack is empty and all nodes are processed.
Implementation
import java.util.*;
class Solution {
public List inorderTraversal(TreeNode root) {
List result = new ArrayList<>();
Stack stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current); // Push left nodes onto the stack
current = current.left;
}
current = stack.pop(); // Pop the top node
result.add(current.val); // Process the node
current = current.right; // Move to the right child
}
return result;
}
}
Complexity Analysis
- Time Complexity:
O(n), wherenis the number of nodes in the tree. Each node is visited exactly once. - Space Complexity:
O(h), wherehis the height of the tree. This accounts for the stack used in recursion or the iterative solution.
Applications of Inorder Traversal
- Binary Search Trees: Inorder traversal produces a sorted sequence of elements.
- Expression Trees: Generates infix expressions.
- Tree Validation: Validates the structure and properties of binary trees.
Common Mistakes
- Not initializing the stack in the iterative solution.
- Failing to handle null nodes, which can lead to runtime errors.
- Confusing the order of traversal with preorder or postorder traversal.
Edge Cases
- An empty tree (should return an empty list).
- A single-node tree (should return a list with the single node's value).
- A tree with only left or right children (should handle traversal correctly).
Sample Outputs
Example 1
Tree:
1
\
2
/
3
Inorder traversal:
[1, 3, 2]
Example 2
Tree:
5
/ \
3 8
/ \
2 4
Inorder traversal:
[2, 3, 4, 5, 8]
Conclusion
Binary Tree Inorder Traversal is a versatile and widely used traversal technique. Its significance in binary search trees and expression trees makes it an essential concept in computer science. By mastering both recursive and iterative approaches, you will have the flexibility to tackle a variety of tree-based problems effectively.
To practice more problems related to tree traversal, visit LeetCode or GeeksforGeeks.
