Binary TreesProblem 6 of 35

Inorder Traversal of a tree both using recursion and Iteration

Brute Force
Time: O(n)
Space: O(n)
Optimal
Time: O(n)
Space: O(1)

Problem Statement

Given a binary tree, perform inorder traversal (Left -> Root -> Right) and return the list of node values. Implement both recursive and iterative approaches.

Example:

1 / \ 2 3 / \ 4 5
  • Input: Root of the above tree
  • Output: [4, 2, 5, 1, 3]

Approach 1: Recursive (Simple DFS)

Intuition

Follow the inorder pattern: traverse left subtree, visit root, traverse right subtree.

Algorithm

  1. Recursively traverse left subtree
  2. Process/visit the current node
  3. Recursively traverse right subtree
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public void inorderRecursive(TreeNode root, List<Integer> result) {
        if (root == null) return;
        
        inorderRecursive(root.left, result);   // Left
        result.add(root.val);                   // Root
        inorderRecursive(root.right, result);  // Right
    }
    
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderRecursive(root, result);
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node once
  • Space Complexity: O(n) - Recursion stack for skewed tree

Approach 2: Iterative (Using Stack)

Intuition

Use an explicit stack to simulate the recursion. Go as left as possible, then process node, then go right.

Algorithm

  1. Initialize an empty stack
  2. Go to the leftmost node, pushing all nodes onto stack
  3. Pop a node, process it, then go to its right subtree
  4. Repeat until stack is empty and current is null
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> inorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        
        while (current != null || !stack.isEmpty()) {
            // Go to the leftmost node
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            
            // Process the node
            current = stack.pop();
            result.add(current.val);
            
            // Go to right subtree
            current = current.right;
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node once
  • Space Complexity: O(n) - Stack can hold all nodes in worst case

Approach 3: Optimal (Morris Traversal - No Extra Space)

Intuition

Use threaded binary tree concept. Create temporary links (threads) to traverse without stack. Find inorder predecessor and create a link to current node.

Algorithm

  1. If left child is null, process node and go right
  2. If left child exists, find inorder predecessor (rightmost in left subtree)
  3. If predecessor's right is null, create thread and go left
  4. If predecessor's right points to current, remove thread, process node, go right
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> inorderMorris(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode current = root;
        
        while (current != null) {
            if (current.left == null) {
                // No left subtree, process current and go right
                result.add(current.val);
                current = current.right;
            } else {
                // Find inorder predecessor
                TreeNode predecessor = current.left;
                while (predecessor.right != null && 
                       predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    // Create thread
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Thread exists, remove it and process current
                    predecessor.right = null;
                    result.add(current.val);
                    current = current.right;
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each edge is traversed at most twice
  • Space Complexity: O(1) - No extra space used (modifies tree temporarily)

Key Takeaways

  1. Inorder = Left -> Root -> Right (gives sorted order for BST)
  2. Recursive approach is simple but uses O(n) stack space
  3. Iterative approach uses explicit stack, easier to control
  4. Morris Traversal achieves O(1) space by using threads
  5. Morris traversal temporarily modifies the tree but restores it
Previous
Mirror of a tree
Next
Preorder Traversal of a tree both using recursion and Iteration