Domain 2MediumCORE

Binary Tree Inorder Traversal

We are given the root of a binary tree and need to return its values in inorder traversal order (Left -> Root -> Right).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Stack#Tree

94. Binary Tree Inorder Traversal

Model: qwen3.5:9b
Topics: Hash Table,Stack,Tree
FAANG asked: 1
Acceptance rate: 66.3%


Problem Breakdown

We are given the root of a binary tree and need to return its values in inorder traversal order (Left -> Root -> Right).

  • Inputs: A TreeNode object representing the root, which can be empty (None).
  • Outputs: A list of integers containing node values.
  • Constraints: Node count is small [0, 100], values are between -100 and 100.
  • Implicit Edge Cases: An empty tree (root is None), a single-node tree, or trees that are heavily skewed to the left or right. We must ensure our solution handles these without crashing on recursion depth limits (though unlikely with N=100) and correctly processes null pointers during traversal.

Intuition

The recursive definition of inorder traversal is straightforward: traverse left subtree, visit node, traverse right subtree. However, the follow-up asks for an iterative approach to avoid using system stack space implicitly via function calls.

To simulate recursion iteratively, we need a data structure that keeps track of our path down the tree when moving left and allows us to backtrack up (visit nodes) once the left branch is exhausted. A Stack fits this perfectly because it follows LIFO order—when we go deep into the left subtree, we push ancestors onto the stack; when we hit a null or finish processing a node’s right side, we pop from the stack and visit that ancestor.

The core insight: We only “visit” (add to result) a node after its entire left subtree has been processed. The stack holds nodes waiting for their right subtrees to be visited.

Approach

  1. Initialize an empty stack list and a pointer curr set to the root.
  2. Use a loop that continues as long as there is either a current node or items in the stack (meaning we haven’t finished traversing).
  3. Go Left: While curr exists, push it onto the stack and move curr to its left child (left). This simulates descending down the tree until we hit a leaf’s leftmost branch.
  4. Visit & Backtrack: Once curr is null (we reached the bottom of a subtree), pop from the stack. The popped node is now “visited” because its left side is done and it has no right child yet or we are processing it before moving to its right. Add this value to our result list, then move curr to the popped node’s right child (node.right).
  5. Repeat until both stack and current pointer are exhausted.

Complexity Analysis

  • Time: O(N)O(N) where N is the number of nodes. We visit every node exactly once (pushed onto stack, processed as leftmost, then popped).
  • Space: O(H)O(H) for the explicit stack space, where H is the height of the tree. In a balanced tree this is O(log⁡N)O(\log N); in a skewed tree it degrades to O(N)O(N). Given constraints (N <= 100), memory usage is negligible but theoretically optimal compared to recursion which also uses O(H). However, iterative solutions are preferred for production environments as they avoid Python’s default recursion limit and function call overhead.

Solution

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from typing import List

class Solution:
    def inorderTraversal(self, root: 'TreeNode') -> List[int]:
        result = []
        stack = []
        curr = root
        
        while curr or stack:
            # Traverse as far left as possible and push nodes to stack
            if curr:
                stack.append(curr)
                curr = curr.left
            
            else:
                curr = stack.pop()
                result.append(curr.val)
                
                # Move to right child of the popped node and continue loop
                curr = curr.right
                
        return result

Edge Cases Handled

  • Empty Tree: If root is None, the initial check in while curr or stack fails immediately (both false), returning an empty list. Correctly handles Example 2.
  • Single Node: Pushes root to stack, goes left (null), pops root, adds value, moves right (null). Loop terminates after one iteration of processing. Returns [val]. Handles Example 3.
  • Skewed Trees:
    • Left-skewed: Stack grows deep as we push every node; popping happens immediately on each step back up the left spine. Correctly reverses order logic to match inorder (L-R).
    • Right-skewed: For a tree where nodes only have right children, curr becomes null after pushing because there is no left child. We pop and visit the node before moving to its right child in the next iteration. This ensures we process them in order: Root -> Right Child (since Left was empty).
  • Negative Values: The code treats values as integers; no special handling needed for negative numbers in Python lists or comparisons.