Problem Statement #

Given a binary tree, return the inorder traversal of its nodes’ values.

Inorder traversal visits nodes in the following order: Left → Root → Right

Example #

For a binary tree:

    1
   / \
  2   3
 / \
4   5

The inorder traversal would return: [4, 2, 5, 1, 3]

Solution: Recursive Approach #

var inorderTraversal = function(root) {
    // Recursive approach
    let result = [];
    if (root === null) {
        return result;
    }
    
    // Go left node
    if (root.left) {
        result = result.concat(inorderTraversal(root.left));
    }
    
    console.log("adding ", root.val);
    result = result.concat([root.val]);
    
    if (root.right) {
        result = result.concat(inorderTraversal(root.right));
    }
    
    // console.log("result ", result);
    return result;
};

Understanding the Approach #

What is Inorder Traversal? #

Inorder traversal is a depth-first search (DFS) algorithm that visits nodes in a specific order. Starting from the leftmost (deepest) node, it traverses the tree from left to right, processing nodes at the lowest depths first before moving up.

This traversal is particularly useful for binary search trees (BSTs), as it returns values in sorted ascending order.

The Recursive Strategy #

The recursive approach follows a simple three-step pattern:

1. Recurse on the left subtree - Visit all nodes in the left branch first
2. Process the current node - Add the current node’s value to the result
3. Recurse on the right subtree - Visit all nodes in the right branch last

This pattern naturally follows the “Left → Root → Right” order that defines inorder traversal.

Code Breakdown #

Let’s analyze the solution step by step to understand how it works.

Step 1: Initialize and Handle Base Case #

let result = [];
if (root === null) {
    return result;
}

What’s happening here:

• We initialize result as an empty array that will accumulate all node values
• The base case (stopping condition) checks if the current node is null
• When we reach a null node (meaning we’ve gone past a leaf node), we return an empty array
• This base case is crucial for the recursion to terminate properly

Step 2: Traverse Left Subtree #

if (root.left) {
    result = result.concat(inorderTraversal(root.left));
}

What’s happening here:

• We check if a left child exists before recursing
• If it exists, we recursively call inorderTraversal on the left subtree
• The recursive call returns an array containing all values from that subtree
• We concatenate this array onto our result array
• This ensures all left subtree values are added before the current node

Why this approach: We use concatenation to maintain uniformity between left and right child processing, and to avoid conditional checks for uninitialized variables.

Step 3: Process Current Node #

console.log("adding ", root.val);
result = result.concat([root.val]);

What’s happening here:

• After processing the entire left subtree, we process the current node
• We add the current node’s value to our result array
• The console.log helps visualize the order of processing during execution
• Note that [root.val] is wrapped in an array so it can be concatenated

Important note: This is where you would perform any “processing” operation on the node. For this problem, we’re simply collecting values, but you could perform other operations here.

Step 4: Traverse Right Subtree #

if (root.right) {
    result = result.concat(inorderTraversal(root.right));
}

What’s happening here:

• We check if a right child exists
• If it exists, we recursively call inorderTraversal on the right subtree
• The returned array is concatenated onto our result
• This ensures all right subtree values are added after the current node

Step 5: Return the Result #

return result;

What’s happening here:

• We return the result array containing all values from:
  • The entire left subtree
  • The current node
  • The entire right subtree
• This array is passed back up the call stack to be concatenated with parent results

How the Recursion Works: A Visual Example #

Let’s trace through the execution for a simple tree:

    2
   / \
  1   3

Execution flow:

1. Call inorderTraversal(2)

   • root.left exists, so recurse on node 1

2. Call inorderTraversal(1)

   • root.left is null, skip
   • Add 1 to result: result = [1]
   • root.right is null, skip
   • Return [1]

3. Back to inorderTraversal(2)

   • Concatenate left result: result = [1]
   • Add current node: result = [1, 2]
   • root.right exists, so recurse on node 3

4. Call inorderTraversal(3)

   • root.left is null, skip
   • Add 3 to result: result = [3]
   • root.right is null, skip
   • Return [3]

5. Back to inorderTraversal(2)

   • Concatenate right result: result = [1, 2, 3]
   • Return [1, 2, 3]

Complexity Analysis #

Time Complexity: O(n) #

• We visit each node exactly once
• At each node, we perform constant-time operations (concatenation is O(k) where k is array size, but amortized across all nodes is still O(n) total)

Space Complexity: O(h) #

• The recursion call stack uses space proportional to the tree height h
• In the worst case (skewed tree), h = n, giving O(n) space
• In the best case (balanced tree), h = log(n), giving O(log n) space
• The result array uses O(n) space, but this is required for the output

Alternative Approach: Iterative Solution #

While the recursive approach is elegant and intuitive, an iterative solution using a stack can also be implemented:

var inorderTraversalIterative = function(root) {
    let result = [];
    let stack = [];
    let current = root;
    
    while (current !== null || stack.length > 0) {
        // Go to the leftmost node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        
        // Current is null, so we pop from stack
        current = stack.pop();
        result.push(current.val);
        
        // Visit right subtree
        current = current.right;
    }
    
    return result;
};

When to use iterative vs recursive:

• Recursive: Cleaner, more intuitive, easier to understand and maintain
• Iterative: No risk of stack overflow for very deep trees, slightly better space complexity in practice

Key Takeaways #

• Inorder traversal follows the pattern: Left → Root → Right
• For binary search trees, inorder traversal returns values in sorted order
• The recursive approach naturally mirrors the traversal pattern
• The base case (null node) is essential for proper termination
• Each recursive call returns an array that gets concatenated with parent results
• Time complexity is O(n) and space complexity is O(h) for the call stack

Practice Tips #

To master inorder traversal:

1. Draw it out: Visualize the tree and trace the execution manually
2. Compare with other traversals: Learn preorder (Root → Left → Right) and postorder (Left → Right → Root) to see the differences
3. Implement iteratively: Try writing the iterative version to deepen your understanding
4. Apply to BSTs: Practice using inorder traversal to validate or extract sorted values from BSTs

Understanding inorder traversal is fundamental to working with binary trees and forms the basis for many more complex tree algorithms.