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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Inorder Traversal

Difficulty: Easy

Problem Description

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Key Insights

  • Inorder traversal visits nodes in the order: left subtree, root, right subtree.
  • This problem can be solved both recursively and iteratively.
  • The iterative approach typically uses a stack to keep track of nodes.

Space and Time Complexity

Time Complexity: O(n) - Each node is processed once. Space Complexity: O(h) - The space complexity is O(h) for the stack, where h is the height of the tree.

Solution

To solve the problem, we can use an iterative approach with a stack. We will traverse the left subtree until we reach a leaf node, pushing each node onto the stack. Once we reach a null left child, we pop the node from the stack, add its value to the result, and then traverse its right subtree. This continues until all nodes have been processed.

Code Solutions

def inorderTraversal(root):
    result = []
    stack = []
    current = root
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
        
    return result
← Back to All Questions