LeetCode 94: Binary Tree Inorder Traversal Solution

Master LeetCode problem 94 (Binary Tree Inorder Traversal), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

94. Binary Tree Inorder Traversal

Easy

Stack Tree Depth-First Search Binary Tree

Problem Explanation

Explanation

To perform an inorder traversal of a binary tree iteratively, we can use a stack to simulate the recursive call stack. The basic idea is to start at the root and traverse all the way to the leftmost node, pushing all the nodes encountered along the way onto the stack. Then, we pop nodes from the stack, process them, and move to their right child if it exists. We repeat this process until the stack is empty and all nodes have been processed.

Algorithm:

Initialize an empty stack and a list to store the inorder traversal result.
Start at the root node and iterate until both the current node and the stack are not empty.
While the current node is not null, push it onto the stack and move to its left child.
Once the current node becomes null, pop a node from the stack, process it (add its value to the result list), and move to its right child.
Repeat steps 3 and 4 until the stack is empty.

Time Complexity:

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity is also O(n) in the worst case due to the stack used for traversal.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 94 (Binary Tree Inorder Traversal)?

This page provides optimized solutions for LeetCode problem 94 (Binary Tree Inorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 94 (Binary Tree Inorder Traversal)?

The time complexity for LeetCode 94 (Binary Tree Inorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 94 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 94 in Java, C++, or Python.

Back to LeetCode Solutions