Binary Tree Inorder Traversal easy

Problem Statement

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

Example 1

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

Example 2

Input: root = [] Output: []

Steps

The inorder traversal of a binary tree follows the order: left subtree, root, right subtree. We can achieve this recursively or iteratively. The iterative approach generally offers better space complexity in some cases, especially for deeply unbalanced trees.

1. Recursive Approach:

   • Define a recursive helper function that takes a node as input.
   • If the node is null, return an empty array.
   • Recursively traverse the left subtree.
   • Add the node's value to the result.
   • Recursively traverse the right subtree.
   • Concatenate the results from the left subtree, the node's value, and the right subtree.

2. Iterative Approach:

   • Use a stack to simulate the recursion.
   • Initialize an empty stack and an empty result array.
   • While the stack is not empty or the current node is not null:
     • While the current node is not null: push the current node onto the stack and move to its left child.
     • Pop the top node from the stack.
     • Add the node's value to the result array.
     • Move to the right child of the popped node.

Explanation

Both approaches follow the inorder traversal principle. The recursive approach is more concise and easier to understand, but it might lead to stack overflow errors for very deep trees. The iterative approach avoids this potential issue by explicitly managing the stack.

Code (TypeScript)

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number;
 *     left: TreeNode | null;
 *     right: TreeNode | null;
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    // Recursive Approach:
    // const result: number[] = [];
    // const traverse = (node: TreeNode | null) => {
    //     if (node === null) return;
    //     traverse(node.left);
    //     result.push(node.val);
    //     traverse(node.right);
    // };
    // traverse(root);
    // return result;


    //Iterative Approach:
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let currentNode: TreeNode | null = root;

    while(currentNode !== null || stack.length > 0){
        while(currentNode !== null){
            stack.push(currentNode);
            currentNode = currentNode.left;
        }
        currentNode = stack.pop();
        result.push(currentNode.val);
        currentNode = currentNode.right;
    }

    return result;
};

Complexity

Recursive Approach:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N.

Iterative Approach:

• Time Complexity: O(N) - We visit each node once.
• Space Complexity: O(H) - The space used by the stack is proportional to the height of the tree. In the worst case (a skewed tree), H could be N, but it's generally better than the recursive approach for deep trees. In the best case (a balanced tree), H is log₂(N).