94. Binary Tree Inorder Traversal

Solution 1: Recursive

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root, ans):
            if not root:
                return
            dfs(root.left, ans)
            ans.append(root.val)
            dfs(root.right, ans)
        ans = []
        dfs(root, ans)
        return ans

Time Complexity: O(N)
Space Complexity: O(N) // Recursive call stack

Solution 2: Iterative

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = []
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                top = stack.pop()
                ans.append(top.val)
                root = top.right
        return ans

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31381/Python-recursive-and-iterative-solutions.