Problem statement

https://binarysearch.com/problems/Inorder-Traversal/

Solution

Equal to Leetcode 0094. Binary Tree Inorder Traversal.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root):
        stack = []
        result = []
        curr = root
        
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right
            
        return result