Complexity Analysis

• Time Complexity: $O(N^2)$. In languages where arrays or lists are immutable or require resizing (like Python lists or Java ArrayLists), concatenating two lists of size $K$ takes $O(K)$ time. In the worst case (a skewed tree), this results in quadratic time complexity.
• Space Complexity: $O(N^2)$. The accumulation of temporary list objects creates excessive memory overhead.

Why It Fails

While this approach may pass the small constraints of LeetCode 94 ($N \le 100$), it fails as a scalable solution. The overhead of list concatenation makes it inefficient for larger trees. It demonstrates a lack of understanding regarding how to maintain state (the result list) across recursive boundaries.

Core Insight for Binary Tree Inorder Traversal

The core insight for solving LeetCode 94 efficiently lies in recognizing the recursive nature of the tree data structure. A binary tree is defined recursively: a tree is a node pointing to two smaller trees (left and right).

The Recursive Inorder Traversal pattern enforces a strict invariant:

1. We cannot process (add to the result list) a node u until u.left and all its descendants have been fully processed.
2. We cannot begin processing u.right until u itself has been processed.

This logic suggests a Depth-First Search (DFS) approach. By using the system call stack (via recursion), we can "pause" the processing of the current node, dive deep into the left subtree, and resume strictly when the left side is finished. We pass a single shared data structure (a list or vector) through the recursion to collect values, avoiding the $O(N^2)$ concatenation cost of the brute force approach.

Visual Description: Imagine the execution flow as a path tracing the outline of the tree. The algorithm starts at the root and immediately moves to the left child, suspending the root's processing. This continues until a leaf is reached. Upon hitting a null left child, the recursion "bounces" back to the leaf node, adds its value, and then attempts to go right. If the right child is null, it returns to the parent. The values are collected precisely at the moment the recursion returns from the left child but before it enters the right child.

Algorithm Strategy: Tree DFS - Recursive Inorder Traversal

The strategy relies on a helper function (or a nested function) that takes the current node and a reference to the result list.

1. State Maintenance: We maintain a single collection (List/Vector) that accumulates values. This is passed by reference or accessed via closure scope.
2. Base Case: If the current node is null, stop the recursion and return immediately. This represents reaching the bottom of a branch.
3. Recursive Step (Left): Recursively call the function on node.left. This ensures we go as deep left as possible before doing anything else.
4. Processing: Append node.val to the result list. This happens only after the left recursive call returns.
5. Recursive Step (Right): Recursively call the function on node.right. This ensures the right subtree is processed after the root.

Execution Flow

Let's trace the algorithm on a simple tree: [1, null, 2, 3] (Root is 1, Right is 2, 2's Left is 3).

1. Start: Call dfs(1).
2. Node 1: Call dfs(1.left) -> dfs(null).
3. Null: Base case hit, return to Node 1.
4. Node 1: Add 1 to result. Result: [1].
5. Node 1: Call dfs(1.right) -> dfs(2).
6. Node 2: Call dfs(2.left) -> dfs(3).
7. Node 3: Call dfs(3.left) -> dfs(null). Return.
8. Node 3: Add 3 to result. Result: [1, 3].
9. Node 3: Call dfs(3.right) -> dfs(null). Return.
10. Node 3: Function completes, return to Node 2.
11. Node 2: Add 2 to result. Result: [1, 3, 2].
12. Node 2: Call dfs(2.right) -> dfs(null). Return.
13. Node 2: Function completes, return to Node 1.
14. Node 1: Function completes. Final Result: [1, 3, 2].

Proof of Correctness

The correctness of this approach is proved via structural induction.

• Base Case: For an empty tree (null), the algorithm returns an empty list, which is the correct inorder traversal.
• Inductive Hypothesis: Assume the algorithm correctly produces the inorder traversal for any tree with fewer than $k$ nodes.
• Inductive Step: Consider a tree with $k$ nodes rooted at $R$. The algorithm visits $R.left$, then $R$, then $R.right$. By the hypothesis, the traversal of $R.left$ correctly lists all nodes in the left subtree in order, and similarly for $R.right$. Since the definition of inorder traversal is Inorder(Left) + Root + Inorder(Right), and our algorithm executes exactly these steps in sequence, the result is correct for $k$ nodes.

Reference Implementation

C++ Solution for LeetCode 94

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorderHelper(TreeNode* node, vector<int>& result) {
        if (node == nullptr) {
            return;
        }
        
        // Step 1: Traverse Left Subtree
        inorderHelper(node->left, result);
        
        // Step 2: Process Current Node
        result.push_back(node->val);
        
        // Step 3: Traverse Right Subtree
        inorderHelper(node->right, result);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorderHelper(root, result);
        return result;
    }
};

Java Solution for LeetCode 94

java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        
        // Step 1: Traverse Left Subtree
        dfs(node.left, result);
        
        // Step 2: Process Current Node
        result.add(node.val);
        
        // Step 3: Traverse Right Subtree
        dfs(node.right, result);
    }
}

Python Solution for LeetCode 94

python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        
        def dfs(node):
            if not node:
                return
            
            # Step 1: Traverse Left Subtree
            dfs(node.left)
            
            # Step 2: Process Current Node
            result.append(node.val)
            
            # Step 3: Traverse Right Subtree
            dfs(node.right)
            
        dfs(root)
        return result