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 order: left subtree, root, right subtree. We can achieve this recursively or iteratively. Here's a recursive approach:

1. Base Case: If the root is null, return an empty list.
2. Recursive Step:
   • Recursively traverse the left subtree and add the result to the list.
   • Add the value of the root node to the list.
   • Recursively traverse the right subtree and add the result to the list.
   • Return the combined list.

Explanation

The recursive approach elegantly implements the inorder traversal definition. The function processes the left subtree, then the root, and finally the right subtree, ensuring the correct order. The base case handles empty trees gracefully.

Code (C#)

using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
        IList<int> result = new List<int>();
        InorderTraversalRecursive(root, result);
        return result;
    }

    private void InorderTraversalRecursive(TreeNode node, IList<int> result) {
        if (node == null) {
            return;
        }

        InorderTraversalRecursive(node.left, result);
        result.Add(node.val);
        InorderTraversalRecursive(node.right, result);
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly 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 can be equal to N, resulting in O(N) space complexity. In the best case (a balanced tree), H is log₂(N), resulting in O(log N) space complexity.