Binary Tree Inorder Traversal Interview Question for Meta

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

For example:

Consider the following binary tree:

What is the inorder traversal of this tree? The expected output is [1, 3, 2].

Now consider a more complex tree:

What is the inorder traversal of this tree? The expected output is [4, 2, 6, 5, 7, 1, 3, 8].

Implement a function that takes the root of a binary tree as input and returns a list containing the inorder traversal of the tree's nodes' values. Provide both a recursive and an iterative solution, analyze their time and space complexity, and explain how your solutions handle edge cases such as an empty tree or a tree with only one node.

Naive Solution: Recursive Inorder Traversal

The most straightforward approach is to use recursion. The inorder traversal visits the left subtree, then the current node, and finally the right subtree.

def inorder_recursive(root):
    if not root:
        return []
    
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

Big O Analysis

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(N) in the worst case (skewed tree), due to the call stack. In the average case (balanced tree), it's O(log N).

Optimal Solution: Iterative Inorder Traversal

An iterative approach using a stack can avoid the overhead of recursion. The idea is to simulate the recursive calls using a stack.

def inorder_iterative(root):
    result = []
    stack = []
    curr = root
    
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
        
    return result

Big O Analysis

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(N) in the worst case (skewed tree), as the stack might contain all nodes. In the average case (balanced tree), it's O(log N).

Edge Cases

Empty Tree: If the root is None, return an empty list.
Single Node Tree: If the tree contains only the root, return a list containing the root's value.

Code (Python)

Here's the complete Python code incorporating the iterative solution and handling edge cases:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def inorderTraversal(root):
    result = []
    stack = []
    curr = root
    
    while curr or stack:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right
            
    return result