Leetcode 94. Binary Tree Inorder Traversal

Problem

Leetcode 94 - Binary Tree Inorder Traversal

Example:

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

Output: [1,3,2]

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Approach

We can do inorder traversal with DFS.

Here is the Python code for the solution:

class Solution:
    # recursion method
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def inorder(root):
            if not root:
                return

            inorder(root.left)
            res.append(root.val)
            inorder(root.right)   
        
        inorder(root)
        return res  

    # iterative method
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        curr = root

        while curr and stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            res.append(curr)
            curr = curr.right
        
        return res

Time Complexity and Space Complexity

Recursion Method:

Time Complexity: $O(n)$

Space Complexity: $O(n)$

Iterative Method:

Time Complexity: $O(n)$

Space Complexity: $O(n)$