We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Inorder Traversal

Number: 94

Difficulty: Easy

Paid? No

Companies: Meta, Google, Microsoft, Amazon, Bloomberg, Adobe, Apple, Uber

Problem Description

Given the root of a binary tree, return the inorder traversal of its nodes' values. In an inorder traversal, you visit the left subtree first, then the current node, and finally the right subtree. Although a recursive solution is straightforward, the challenge is to implement this traversal iteratively.

Key Insights

  • Inorder traversal pattern: left subtree → node → right subtree.
  • An iterative solution uses a stack to simulate the recursive process.
  • Continuously move to the leftmost node and store nodes in the stack.
  • After reaching a null, backtrack by popping from the stack, process the node, and then explore its right subtree.
  • Handle edge cases such as an empty tree.

Space and Time Complexity

Time Complexity: O(n) - Every node is visited once. Space Complexity: O(n) - In the worst-case scenario (skewed tree), the stack may store all nodes.

Solution

The problem can be solved using an iterative approach that simulates the behavior of recursion with a stack. Start with the root node, then push each left child onto the stack until reaching a null node. Once you hit null, pop the last node from the stack, process it, and then move to its right child. Repeat this process until there are no nodes left to process. This method ensures that nodes are processed in their correct inorder sequence.

Code Solutions

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> list:
        result = []            # List to store inorder traversal
        stack = []             # Stack to simulate recursion
        current = root         # Start with the root node
        
        # Iterate while there are nodes to visit or process
        while current or stack:
            # Reach the left most node of the current subtree
            while current:
                stack.append(current)
                current = current.left
                
            # Current is null; backtrack via the stack
            current = stack.pop()
            result.append(current.val)   # Process current node
            current = current.right      # Consider right subtree
        
        return result
← Back to All Questions