EasyTrees

Inorder Traversal

Inorder tree traversal

Solution Approach

Traverse left subtree, visit node, traverse right subtree. Use recursion or stack for iteration.

Implementation

def inorderTraversal(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result
    
# Iterative approach
def inorderTraversalIter(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

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)

Complexity

Time:O(n)

Space:O(h)

Asked at

GoogleAmazonMicrosoft