LC94. Binary Tree Inorder Traversal¶

Problem Description¶

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

Clarification¶

Definition of inorder traversal

Assumption¶

-

Solution¶

Approach 1 - Recursion¶

This problem can be solved using the classic recursive method by defining a new helper function inorder. In the helper function,

inorder(root.left, values)  # recursively traverse the left subtree
values.append(root.val)  # visit root/parent node
inorder(root.right, values)  # recursively traverse the right subtree

python

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        self.inorder(root, result)
        return result

    def inorder(self, node: Optional[TreeNode], result: List[int]):
        if node is None:
            return

        self.inorder(node.left, result)
        result.append(node.val)
        self.inorder(node.right, result)

Complexity Analysis of Approach 1¶

Time complexity: $O(n)$
The algorithm visits each node exactly once for total $n$ nodes.
Space complexity: $O(n)$
The recursion stack takes $O(n)$ space in the worst case (for example, every node only has left child). In the best case (a balanced binary tree), the recursion stack takes $O(\log n)$ space.

Approach 2 - Iteration with Stack¶

Instead of using recursion, we can traverse the nodes by using stack to store the nodes and pop it up when reaching the end of the left branch.

Python

from collections import deque

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        values = []
        stack = deque()

        curr_node = root
        while curr_node or stack:
            if curr_node:
                stack.append(curr_node)  # (1)
                curr_node = curr_node.left
            else:
                curr_node = stack.pop()
                values.append(curr_node.val)  # (2)
                curr_node = curr_node.right

        return values

To return the root later.
Append after all left children.

Complexity Analysis of Approach 2¶

Time complexity: $O(n)$
Each node (total $n$ nodes) is pushed once to and popped once from the stack. So the time complexity is $O(2n) = O(n)$.
Space complexity: $O(n)$
- In the worst case (for example, every node only has left child), the stack will hold all $n$ nodes.
- In the best case (a balanced binary tree), stack will hold $\log n$ nodes due to the height of the tree.

Approach 3 - Morris Traversal¶

We can use Morris traversal which is similar to the solution in preorder traversal. The only difference is in when to visit node after finding predecessor:

Preorder traversal: visit node when predecessor.right is None (before exploring left), since root/parent needs to be the first (root - left - right) before exploring the left.
Inorder traversal: visit node when predecessor.right is curr_node (after exploring left), since root/parent needs to be middle (left - middle - right).