Binary TreesProblem 7 of 35

Preorder 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 preorder traversal (Root -> Left -> 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: [1, 2, 4, 5, 3]

Approach 1: Recursive (Simple DFS)

Intuition

Follow the preorder pattern: visit root first, then traverse left subtree, finally traverse right subtree.

Algorithm

  1. Process/visit the current node
  2. Recursively traverse left subtree
  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 preorderRecursive(TreeNode root, List<Integer> result) {
        if (root == null) return;
        
        result.add(root.val);                   // Root
        preorderRecursive(root.left, result);   // Left
        preorderRecursive(root.right, result);  // Right
    }
    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderRecursive(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 a stack to simulate recursion. Process current node, push right child first (so left is processed first), then push left child.

Algorithm

  1. Push root onto stack
  2. Pop a node, process it
  3. Push right child, then left child (order matters!)
  4. Repeat until stack is empty
java
import java.util.*;

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

public class Solution {
    public List<Integer> preorderIterative(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 first so left is processed first
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        
        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

Similar to Morris inorder, but process node when first visiting it (before going to left subtree).

Algorithm

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

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

public class Solution {
    public List<Integer> preorderMorris(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) {
                    // First visit - process current, create thread, go left
                    result.add(current.val);
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // Second visit - remove thread, go right
                    predecessor.right = null;
                    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

Key Takeaways

  1. Preorder = Root -> Left -> Right (process root first)
  2. Iterative approach: Push right before left (LIFO order)
  3. Morris Traversal: Process node on first visit (unlike inorder which processes on second visit)
  4. Preorder is useful for creating a copy of tree or prefix expression
  5. The iterative approach for preorder is simpler than inorder
Previous
Inorder Traversal of a tree both using recursion and Iteration
Next
Postorder Traversal of a tree both using recursion and Iteration