Binary Tree Inorder Traversal

Problem Summary

• Given a binary tree, do a DFS Inorder Traversal and return a list of values

Main Concepts Used

• Tree Traversal
• In-order Traversal
• Depth First Traversal

Time & Space Complexity

• Time: $O(n)$ → Reason: Visiting each node
• Space: $O(n)$ → Reason: Storing each node

Recursive Code

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

Iterative Code

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

        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right
        return result

Common Mistakes / Things I Got Stuck On

• Not fully understanding tree traversals