Binary Tree Traversals

Generated on 2025-07-10 02:03:17 Algorithm Cheatsheet for Technical Interviews

---

Binary Tree Traversals Cheatsheet

1. Quick Overview

Binary tree traversals are algorithms that visit (access and/or process) each node in a tree data structure exactly once. They differ based on the order in which nodes are visited. Choosing the right traversal depends on the specific task you need to perform on the tree.

• Inorder Traversal: Left subtree -> Root -> Right subtree (Often used for BSTs to get sorted order)
• Preorder Traversal: Root -> Left subtree -> Right subtree (Often used for creating a copy of the tree or prefix expression evaluation)
• Postorder Traversal: Left subtree -> Right subtree -> Root (Often used for deleting a tree or postfix expression evaluation)
• Level Order Traversal (Breadth-First Search): Visit nodes level by level (Good for finding the shortest path in an unweighted tree)

2. Time & Space Complexity

Traversal	Time Complexity	Space Complexity (Avg)	Space Complexity (Worst)
Inorder	O(N)	O(log N)	O(N)
Preorder	O(N)	O(log N)	O(N)
Postorder	O(N)	O(log N)	O(N)
Level Order	O(N)	O(W)	O(W)

• N = Number of nodes in the tree
• W = Maximum width of the tree (number of nodes at the widest level)
• Worst-case space complexity occurs for skewed trees (linear shape).
• Average-case space complexity occurs for balanced trees.

3. Implementation

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Inorder Traversal (Recursive)
def inorder_recursive(root):
    """Inorder traversal using recursion."""
    result = []
    if root:
        result.extend(inorder_recursive(root.left)) # Traverse left subtree
        result.append(root.val)                     # Visit root
        result.extend(inorder_recursive(root.right)) # Traverse right subtree
    return result
# Time: O(N), Space: O(H) where H is the height of the tree

# Inorder Traversal (Iterative)
def inorder_iterative(root):
    """Inorder traversal using a stack."""
    result = []
    stack = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left  # Go as far left as possible

        curr = stack.pop()  # Visit the node
        result.append(curr.val)
        curr = curr.right # Go to the right subtree

    return result
# Time: O(N), Space: O(H)

# Preorder Traversal (Recursive)
def preorder_recursive(root):
    """Preorder traversal using recursion."""
    result = []
    if root:
        result.append(root.val)                     # Visit root
        result.extend(preorder_recursive(root.left)) # Traverse left subtree
        result.extend(preorder_recursive(root.right))# Traverse right subtree
    return result
# Time: O(N), Space: O(H)

# Preorder Traversal (Iterative)
def preorder_iterative(root):
    """Preorder traversal using a stack."""
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()  # Visit the node
        result.append(node.val)

        # Push right child first, so left child is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result
# Time: O(N), Space: O(H)

# Postorder Traversal (Recursive)
def postorder_recursive(root):
    """Postorder traversal using recursion."""
    result = []
    if root:
        result.extend(postorder_recursive(root.left)) # Traverse left subtree
        result.extend(postorder_recursive(root.right))# Traverse right subtree
        result.append(root.val)                     # Visit root
    return result
# Time: O(N), Space: O(H)

# Postorder Traversal (Iterative - Tricky)
def postorder_iterative(root):
    """Postorder traversal using a stack."""
    if not root:
        return []

    result = []
    stack = [root]
    last_visited = None # Keep track of the last visited node to avoid infinite loops.

    while stack:
        curr = stack[-1] #peek

        # If we are going down the tree, push the children onto the stack
        if not last_visited or last_visited.left == curr or last_visited.right == curr:
            if curr.left:
                stack.append(curr.left)
            elif curr.right:
                stack.append(curr.right)

        # If we are going up the tree from the left node, push the right node if it exists
        elif curr.left == last_visited:
            if curr.right:
                stack.append(curr.right)

        # If we are going up the tree from the right node, or if there is no right node, pop the current node and add to the result
        else:
            result.append(curr.val)
            stack.pop()

        last_visited = curr

    return result
# Time: O(N), Space: O(H)

# Level Order Traversal (Iterative - BFS)
from collections import deque

def levelorder_iterative(root):
    """Level order traversal using a queue (BFS)."""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)  # Store each level as a sublist

    return result
# Time: O(N), Space: O(W)

# Example usage:
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))

print("Inorder (Recursive):", inorder_recursive(root))
print("Inorder (Iterative):", inorder_iterative(root))
print("Preorder (Recursive):", preorder_recursive(root))
print("Preorder (Iterative):", preorder_iterative(root))
print("Postorder (Recursive):", postorder_recursive(root))
print("Postorder (Iterative):", postorder_iterative(root))
print("Level Order:", levelorder_iterative(root))

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

public class TreeTraversals {

    // Inorder Traversal (Recursive)
    public List<Integer> inorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            result.addAll(inorderRecursive(root.left));
            result.add(root.val);
            result.addAll(inorderRecursive(root.right));
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Inorder Traversal (Iterative)
    public List<Integer> inorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Preorder Traversal (Recursive)
    public List<Integer> preorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            result.add(root.val);
            result.addAll(preorderRecursive(root.left));
            result.addAll(preorderRecursive(root.right));
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Preorder Traversal (Iterative)
    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);

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Postorder Traversal (Recursive)
    public List<Integer> postorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            result.addAll(postorderRecursive(root.left));
            result.addAll(postorderRecursive(root.right));
            result.add(root.val);
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Postorder Traversal (Iterative) - Tricky
    public List<Integer> postorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode lastVisited = null;

        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();

            if (lastVisited == null || lastVisited.left == curr || lastVisited.right == curr) {
                if (curr.left != null) {
                    stack.push(curr.left);
                } else if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else if (curr.left == lastVisited) {
                if (curr.right != null) {
                    stack.push(curr.right);
                }
            } else {
                result.add(curr.val);
                stack.pop();
            }
            lastVisited = curr;
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Level Order Traversal (Iterative - BFS)
    public List<List<Integer>> levelOrderIterative(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(currentLevel);
        }
        return result;
    }
    // Time: O(N), Space: O(W)

    public static void main(String[] args) {
        // Example usage:
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));

        TreeTraversals traversals = new TreeTraversals();

        System.out.println("Inorder (Recursive): " + traversals.inorderRecursive(root));
        System.out.println("Inorder (Iterative): " + traversals.inorderIterative(root));
        System.out.println("Preorder (Recursive): " + traversals.preorderRecursive(root));
        System.out.println("Preorder (Iterative): " + traversals.preorderIterative(root));
        System.out.println("Postorder (Recursive): " + traversals.postorderRecursive(root));
        System.out.println("Postorder (Iterative): " + traversals.postorderIterative(root));
        System.out.println("Level Order: " + traversals.levelOrderIterative(root));
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class TreeTraversals {
public:
    // Inorder Traversal (Recursive)
    std::vector<int> inorderRecursive(TreeNode* root) {
        std::vector<int> result;
        if (root) {
            std::vector<int> left = inorderRecursive(root->left);
            result.insert(result.end(), left.begin(), left.end());
            result.push_back(root->val);
            std::vector<int> right = inorderRecursive(root->right);
            result.insert(result.end(), right.begin(), right.end());
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Inorder Traversal (Iterative)
    std::vector<int> inorderIterative(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> stack;
        TreeNode* curr = root;

        while (curr || !stack.empty()) {
            while (curr) {
                stack.push(curr);
                curr = curr->left;
            }
            curr = stack.top();
            stack.pop();
            result.push_back(curr->val);
            curr = curr->right;
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Preorder Traversal (Recursive)
    std::vector<int> preorderRecursive(TreeNode* root) {
        std::vector<int> result;
        if (root) {
            result.push_back(root->val);
            std::vector<int> left = preorderRecursive(root->left);
            result.insert(result.end(), left.begin(), left.end());
            std::vector<int> right = preorderRecursive(root->right);
            result.insert(result.end(), right.begin(), right.end());
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Preorder Traversal (Iterative)
    std::vector<int> preorderIterative(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

        std::stack<TreeNode*> stack;
        stack.push(root);

        while (!stack.empty()) {
            TreeNode* node = stack.top();
            stack.pop();
            result.push_back(node->val);

            if (node->right) {
                stack.push(node->right);
            }
            if (node->left) {
                stack.push(node->left);
            }
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Postorder Traversal (Recursive)
    std::vector<int> postorderRecursive(TreeNode* root) {
        std::vector<int> result;
        if (root) {
            std::vector<int> left = postorderRecursive(root->left);
            result.insert(result.end(), left.begin(), left.end());
            std::vector<int> right = postorderRecursive(root->right);
            result.insert(result.end(), right.begin(), right.end());
            result.push_back(root->val);
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Postorder Traversal (Iterative) - Tricky
    std::vector<int> postorderIterative(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

        std::stack<TreeNode*> stack;
        stack.push(root);
        TreeNode* lastVisited = nullptr;

        while (!stack.empty()) {
            TreeNode* curr = stack.top();

            if (!lastVisited || lastVisited->left == curr || lastVisited->right == curr) {
                if (curr->left) {
                    stack.push(curr->left);
                } else if (curr->right) {
                    stack.push(curr->right);
                }
            } else if (curr->left == lastVisited) {
                if (curr->right) {
                    stack.push(curr->right);
                }
            } else {
                result.push_back(curr->val);
                stack.pop();
            }
            lastVisited = curr;
        }
        return result;
    }
    // Time: O(N), Space: O(H)

    // Level Order Traversal (Iterative - BFS)
    std::vector<std::vector<int>> levelOrderIterative(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;

        std::queue<TreeNode*> queue;
        queue.push(root);

        while (!queue.empty()) {
            int levelSize = queue.size();
            std::vector<int> currentLevel;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                currentLevel.push_back(node->val);

                if (node->left) {
                    queue.push(node->left);
                }
                if (node->right) {
                    queue.push(node->right);
                }
            }
            result.push_back(currentLevel);
        }
        return result;
    }
    // Time: O(N), Space: O(W)
};

int main() {
    // Example usage:
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode* root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));

    TreeTraversals traversals;

    std::cout << "Inorder (Recursive): ";
    std::vector<int> inorderRec = traversals.inorderRecursive(root);
    for (int val : inorderRec) std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Inorder (Iterative): ";
    std::vector<int> inorderIter = traversals.inorderIterative(root);
    for (int val : inorderIter) std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Preorder (Recursive): ";
    std::vector<int> preorderRec = traversals.preorderRecursive(root);
    for (int val : preorderRec) std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Preorder (Iterative): ";
    std::vector<int> preorderIter = traversals.preorderIterative(root);
    for (int val : preorderIter) std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Postorder (Recursive): ";
    std::vector<int> postorderRec = traversals.postorderRecursive(root);
    for (int val : postorderRec) std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Postorder (Iterative): ";
    std::vector<int> postorderIter = traversals.postorderIterative(root);
    for (int val : postorderIter) std::cout << val << " ";
    std::cout << std::endl;

    std::cout << "Level Order: " << std::endl;
    std::vector<std::vector<int>> levelOrder = traversals.levelOrderIterative(root);
    for (const auto& level : levelOrder) {
        for (int val : level) std::cout << val << " ";
        std::cout << std::endl;
    }

    return 0;
}

4. Common Patterns

• Binary Search Trees (BST): Inorder traversal yields nodes in ascending order.
• Expression Trees:
  • Inorder: Infix notation (requires parentheses for correct precedence).
  • Preorder: Prefix notation (Polish notation).
  • Postorder: Postfix notation (Reverse Polish notation).
• Tree Serialization/Deserialization: Preorder traversal is often used as a basis for serialization since it visits the root first, allowing reconstruction of the tree structure.
• Finding a specific node/value: Traversals can be adapted to search for a particular node or value by adding a conditional check within the traversal logic.
• Calculating tree properties: Traversals can be used to calculate tree height, size, sum of nodes, etc.
• Modifying Nodes: Traversals allow you to apply transformations to each node’s value, such as incrementing or changing its data type.

5. Pro Tips

• Iterative vs. Recursive: Recursive solutions are often more concise and easier to understand, but iterative solutions avoid stack overflow issues for very deep trees.
• Space Optimization (Morris Traversal): For inorder traversal, Morris traversal uses threaded binary trees to achieve O(1) space complexity (modifies the tree structure temporarily). This is a more advanced technique.
• Handle Empty Trees: Always check for root == None (or equivalent in your language) at the beginning of your traversal functions to handle empty trees gracefully.
• Understand Stack/Queue Behavior: For iterative solutions, be mindful of how the stack (LIFO) and queue (FIFO) affect the order of node processing. For preorder, push the right child before the left child onto the stack.
• Postorder Iterative Trick: The iterative postorder traversal is the most complex. The key is to keep track of the last visited node and to avoid re-visiting nodes unnecessarily. The last_visited variable in the example code is crucial.
• Level Order and BFS: Level order traversal is Breadth-First Search (BFS) applied to a tree. It’s fundamental for many graph algorithms.

6. Practice Problems

1. LeetCode 94. Binary Tree Inorder Traversal: Given the root of a binary tree, return the inorder traversal of its nodes’ values.
2. LeetCode 102. Binary Tree Level Order Traversal: Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
3. LeetCode 144. Binary Tree Preorder Traversal: Given the root of a binary tree, return the preorder traversal of its nodes’ values.
4. LeetCode 145. Binary Tree Postorder Traversal: Given the root of a binary tree, return the postorder traversal of its nodes’ values.
5. LeetCode 104. Maximum Depth of Binary Tree: Use a traversal (e.g., level order or recursive) to find the maximum depth (height) of a binary tree.

7. Templates

These templates provide a quick starting point for implementing tree traversals.

C++

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class TreeTraversals {
public:
    // Inorder Traversal (Recursive)
    std::vector<int> inorderRecursive(TreeNode* root) {
        std::vector<int> result;
        if (root) {
            // Traverse left
            // Visit Root
            // Traverse right
        }
        return result;
    }

    // Inorder Traversal (Iterative)
    std::vector<int> inorderIterative(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> stack;
        TreeNode* curr = root;

        while (curr || !stack.empty()) {
            // Go as far left as possible
            // Visit Node
            // Go to right subtree
        }
        return result;
    }

    // Preorder Traversal (Recursive)
    std::vector<int> preorderRecursive(TreeNode* root) {
        std::vector<int> result;
        if (root) {
            // Visit root
            // Traverse left
            // Traverse right
        }
        return result;
    }

    // Preorder Traversal (Iterative)
    std::vector<int> preorderIterative(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

        std::stack<TreeNode*> stack;
        stack.push(root);

        while (!stack.empty()) {
            // Visit Node
            // Push right (if exists)
            // Push left (if exists)
        }
        return result;
    }

    // Postorder Traversal (Recursive)
    std::vector<int> postorderRecursive(TreeNode* root) {
        std::vector<int> result;
        if (root) {
            // Traverse left
            // Traverse right
            // Visit root
        }
        return result;
    }

    // Postorder Traversal (Iterative) - Tricky
    std::vector<int> postorderIterative(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

        std::stack<TreeNode*> stack;
        stack.push(root);
        TreeNode* lastVisited = nullptr;

        while (!stack.empty()) {
            TreeNode* curr = stack.top();

            if (!lastVisited || lastVisited->left == curr || lastVisited->right == curr) {
                // Going down the tree
                // Push left or right if available
            } else if (curr->left == lastVisited) {
                // Coming up from left
                // Push right if available
            } else {
                // Coming up from right or no right child
                // Process node
            }
            lastVisited = curr;
        }
        return result;
    }

    // Level Order Traversal (Iterative - BFS)
    std::vector<std::vector<int>> levelOrderIterative(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;

        std::queue<TreeNode*> queue;
        queue.push(root);

        while (!queue.empty()) {
            int levelSize = queue.size();
            std::vector<int> currentLevel;

            for (int i = 0; i < levelSize; i++) {
                // Dequeue node
                // Add to current level
                // Enqueue left and right children
            }
            result.push_back(currentLevel);
        }
        return result;
    }
};

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_recursive(root):
    result = []
    if root:
        # Traverse left
        # Visit root
        # Traverse right
    return result

def inorder_iterative(root):
    result = []
    stack = []
    curr = root

    while curr or stack:
        # Go as far left as possible
        # Visit the node
        # Go to the right subtree
    return result

def preorder_recursive(root):
    result = []
    if root:
        # Visit root
        # Traverse left
        # Traverse right
    return result

def preorder_iterative(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        # Visit the node
        # Push right child first
        # Push left child
    return result

def postorder_recursive(root):
    result = []
    if root:
        # Traverse left
        # Traverse right
        # Visit root
    return result

def postorder_iterative(root):
    if not root:
        return []

    result = []
    stack = [root]
    last_visited = None

    while stack:
        curr = stack[-1]

        if not last_visited or last_visited.left == curr or last_visited.right == curr:
            # Going down the tree
            # Push children if they exist
        elif curr.left == last_visited:
            # Coming up from left subtree
            # Push right if it exists
        else:
            # Coming up from right subtree or no right subtree
            # Visit node

        last_visited = curr

    return result

from collections import deque

def levelorder_iterative(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            # Dequeue node
            # Add to current level
            # Enqueue children
        result.append(current_level)

    return result

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

public class TreeTraversals {

    // Inorder Traversal (Recursive)
    public List<Integer> inorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            // Traverse left
            // Visit root
            // Traverse right
        }
        return result;
    }

    // Inorder Traversal (Iterative)
    public List<Integer> inorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            // Go as far left as possible
            // Visit the node
            // Go to the right subtree
        }
        return result;
    }

    // Preorder Traversal (Recursive)
    public List<Integer> preorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            // Visit root
            // Traverse left
            // Traverse right
        }
        return result;
    }

    // Preorder Traversal (Iterative)
    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()) {
            // Visit the node
            // Push right child (if exists)
            // Push left child (if exists)
        }
        return result;
    }

    // Postorder Traversal (Recursive)
    public List<Integer> postorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            // Traverse left
            // Traverse right
            // Visit root
        }
        return result;
    }

    // Postorder Traversal (Iterative) - Tricky
    public List<Integer> postorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode lastVisited = null;

        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();

            if (lastVisited == null || lastVisited.left == curr || lastVisited.right == curr) {
                // Going down the tree
                // Push left or right if available
            } else if (curr.left == lastVisited) {
                // Coming up from left
                // Push right if available
            } else {
                // Coming up from right or no right child
                // Process node
            }
            lastVisited = curr;
        }
        return result;
    }

    // Level Order Traversal (Iterative - BFS)
    public List<List<Integer