Problem statement

https://leetcode.com/problems/binary-tree-inorder-traversal/

Solution

Recursion solution is indeed trivial. If we want to avoid it, we need to use stack: the idea of one iteration is to put to stack as much left children as possible, and if not, than pop value, add it to stack and go the right children.

Complexity

Time complexity is O(n) and space complexity is O(n) as well to keep result.

Code

class Solution:
    def inorderTraversal(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

Remark

There is so-called Morris Traversal, which has only O(1) memory (not including answer)