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: []

Example 3:

Input: root = [1]
Output: [1]

Steps

The inorder traversal of a binary tree follows the pattern: Left -> Root -> Right. We can achieve this recursively or iteratively. Here's a breakdown of the recursive approach:

1. Base Case: If the current node is null, return an empty list.
2. Recursive Calls:
   • Recursively traverse the left subtree.
   • Add the value of the current node to the result list.
   • Recursively traverse the right subtree.
3. Combine Results: Combine the results from the left subtree, the current node's value, and the right subtree into a single list and return it.

Explanation

The recursive approach elegantly mirrors the definition of inorder traversal. Each recursive call handles a subtree, ensuring that the left subtree is processed before the root, and the right subtree is processed after. The base case prevents infinite recursion when reaching the end of branches.

Code (Java)

import java.util.ArrayList;
import java.util.List;

/**
 * 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<>();
        inorderHelper(root, result);
        return result;
    }

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

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: O(H) in the worst case, 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 equal to N. In the best case (a balanced tree), H would be log₂(N). An iterative approach using a stack would have O(H) space complexity as well.