Inorder Traversal (Morris Inorder Traversal)

Dec 18, 2024 • 4 mins read

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

The LeetCode problem "Binary Tree Inorder Traversal" involves traversing a binary tree in a specific order. This type of question is a fundamental one in understanding tree data structures, as tree traversal algorithms form the basis of many more complex operations on trees.

The task requires performing an inorder traversal of a binary tree. In an inorder traversal, for each node, the left subtree is visited first, then the node itself, and finally, the right subtree. The problem URL is here.

Understanding the Problem

In the inorder traversal, you need to visit the nodes in the "left-root-right" order. For example, given a binary tree:

The inorder traversal would yield: [1, 3, 2]. To solve this, you would start with the leftmost node and work your way up and over to the rightmost node.

Key DSA Concepts and Theory

Binary Tree

Binary Tree: A tree data structure where each node has at most two children referred to as the left child and the right child.

Tree Traversal

Inorder Traversal: Particularly important for binary search trees. It visits nodes in a non-decreasing order. The algorithm can be implemented recursively or iteratively using a stack.

Recursive vs Iterative Traversal

Recursive Traversal: Simpler and naturally follows the definition of the traversal. It uses system call stack space.
Iterative Traversal: More complex but necessary to avoid stack overflow for extremely deep trees. It employs an explicit stack to simulate the recursive approach.

Solution Approach

Recursive Solution

The recursive approach is straightforward. It involves:

Traversing the left subtree recursively.
Visiting the root node.
Traversing the right subtree recursively.

Here's how it looks in C++:

// C++ Recursive Approach
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorderHelper(root, result);
        return result;
    }
    
    void inorderHelper(TreeNode* node, vector<int>& result) {
        if (node == nullptr) {
            return;
        }
        inorderHelper(node->left, result);
        result.push_back(node->val);
        inorderHelper(node->right, result);
    }
};

And in Java:

// Java Recursive Approach
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }

    private void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        inorderHelper(node.left, result);
        result.add(node.val);
        inorderHelper(node.right, result);
    }
}

Iterative Solution

The iterative solution uses a stack to simulate recursive behavior:

Start from the root and push nodes onto the stack as you travel left.
Visit the node at the top of the stack, then move to the right.

Here is the C++ implementation:

// C++ Iterative Approach
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        TreeNode* current = root;

        while (current != nullptr || !stk.empty()) {
            while (current != nullptr) {
                stk.push(current);
                current = current->left;
            }
            current = stk.top();
            stk.pop();
            result.push_back(current->val);
            current = current->right;
        }

        return result;
    }
};

And the Java equivalent:

// Java Iterative Approach
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }

        return result;
    }
}

Time and Space Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the binary tree. Every node is visited once.
Space Complexity:
- Recursive: O(h), where h is the height of the tree, due to the recursion stack.
- Iterative: O(h), due to the stack used for traversal, where h is the tree height.

Common Mistakes to Avoid

Null Checks: Failing to check for null nodes can lead to runtime errors.
Incorrect Stack Usage: Not correctly maintaining the stack during iterative traversal.
Misordering Nodes: Ensure that nodes are visited in "left-root-right" order in inorder traversal.