Algorithm-Day37-Binary-Tree-Inorder-Traversal-lc-94

Posted on In , Views:

🧩 Problem Description

Given the root of a binary tree, return its inorder traversal as a list of integers.

Inorder traversal order: left → root → right

💬 Example

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

💡 Approach 1: Recursive DFS

The simplest way is to use recursion.
Visit:

  1. Left subtree
  2. Current node
  3. Right subtree

🔢 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    private void dfs(TreeNode node, List<Integer> res) {
        if (node == null) return;
        dfs(node.left, res);
        res.add(node.val);
        dfs(node.right, res);
    }
}

💡 Approach 2: Iterative with Stack

Use a stack to simulate the recursion.

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }

        return res;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — each node is visited once
  • Space Complexity:
    • Recursive: O(h) stack depth (h = height)
    • Iterative: O(h) explicit stack

✍️ Summary

  • Learn both recursive and iterative versions
  • Foundation for tree problems like:
    • lc-144: Preorder traversal
    • lc-145: Postorder traversal
    • lc-230: Kth Smallest in BST

Tree traversal mastery is essential for any tree-based problem.