065.md

94. Binary Tree Inorder Traversal

Difficulty: 🟢 Easy

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

Examples:

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• 100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Solutions

O(n) solution

Python 3

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

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        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

The given solution provides an iterative approach to perform an inorder traversal of a binary tree.

Here is an overview of the solution:

1. Initialize an empty list called result to store the inorder traversal values.
2. Initialize an empty stack called stack.
3. Set a current node curr to the root of the binary tree.
4. While curr is not None or stack is not empty, do the following:
   • While curr is not None, push curr onto stack and update curr to curr's left child. This step traverses to the leftmost node of the current subtree.
   • Pop the top node curr from stack and append its value to result. This step represents visiting the current node.
   • Set curr to the right child of the popped node. This step moves to the right child of the current node if it exists.
5. Return result, which will contain the inorder traversal values.

The solution uses an iterative approach and simulates the recursive process of an inorder traversal using a stack to store nodes.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of nodes in the binary tree. We visit each node once during the traversal.

The space complexity is O(h), where h is the height of the binary tree. In the worst case, the height of the binary tree can be O(n) for a skewed tree, resulting in O(n) space complexity. However, for a balanced tree, the height is O(log n), resulting in O(log n) space complexity.

Summary

The given solution efficiently performs an inorder traversal of a binary tree using an iterative approach. It uses a stack to simulate the recursive process and stores the inorder traversal values in a list. The solution has a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes in the binary tree and h is the height of the tree.

NB: If you want to get community points please suggest solutions in other languages as merge requests.