Binary Tree Inorder Traversal

Inorder traversal is a fundamental tree traversal algorithm that visits nodes in a specific order: left subtree, root, right subtree. This algorithm is widely used in various applications, including sorting binary search trees and evaluating expressions represented as trees. Your task is to implement an algorithm that performs an inorder traversal of a given binary tree and returns the nodes' values in the correct order.

Problem Description

Given the root node of a binary tree, perform an inorder traversal and return a list containing the values of the nodes in the order they are visited. The inorder traversal should visit all nodes in the tree, ensuring the left subtree is processed before the root, and the right subtree is processed after the root.

Key Requirements:

• The algorithm should handle both empty trees (root is null) and trees with varying depths and structures.
• The output list should contain the node values in the correct inorder sequence.
• The algorithm should be recursive or iterative (your choice).

Expected Behavior:

The function should take the root node of a binary tree as input and return a list of integers representing the inorder traversal of the tree.

Edge Cases to Consider:

• Empty tree (root is null): Return an empty list.
• Tree with only a root node: Return a list containing only the root node's value.
• Skewed trees (left-skewed or right-skewed): Ensure the algorithm correctly traverses these structures.
• Binary Search Tree (BST): While not a requirement, consider how the algorithm behaves on a BST.

Examples

Example 1:

Input:
    1
   / \
  2   3

Output: [2, 1, 3] Explanation: The inorder traversal visits the left subtree (2), then the root (1), and finally the right subtree (3).

Example 2:

Input:
    1
   / \
  2   null
 / \
3   4

Output: [3, 2, 4, 1] Explanation: The left subtree (2) is traversed inorder (3, 2, 4), then the root (1) is visited.

Example 3: (Edge Case - Empty Tree)

Input: null
Output: []
Explanation: An empty tree results in an empty list.

Constraints

• The tree can contain up to 1000 nodes.
• Node values are integers.
• The algorithm should have a time complexity of O(N), where N is the number of nodes in the tree.
• The algorithm should have a space complexity of O(H) in the average case, where H is the height of the tree (for recursive solutions). Iterative solutions may have a space complexity of O(N) in the worst case (skewed tree).

Notes

• You can represent the binary tree using any suitable data structure (e.g., a class with val, left, and right attributes).
• Consider using recursion or an iterative approach (e.g., using a stack) to implement the inorder traversal.
• Think about how to handle null nodes (left or right children) gracefully.
• The order of elements in the output list is crucial. Ensure it strictly adheres to the inorder traversal sequence.
• Focus on clarity and efficiency in your solution.