Binary Tree Inorder Traversal

This challenge focuses on traversing a binary tree in a specific order: inorder. Inorder traversal is fundamental for many tree-related algorithms, such as converting a binary search tree to a sorted array or evaluating expression trees. Your task is to implement an inorder traversal and return the values of the nodes in the visited order.

Problem Description

You are given the root of a binary tree. You need to perform an inorder traversal of the tree and return a list of the values of the nodes in the order they are visited.

An inorder traversal visits nodes in the following order:

1. Traverse the left subtree.
2. Visit the current node.
3. Traverse the right subtree.

Key Requirements:

• The function should accept the root of a binary tree as input.
• The function should return a list (or array) of node values.
• The order of values in the list must strictly follow the inorder traversal pattern.

Expected Behavior:

• For a given binary tree, the output list should contain the values of the nodes visited in the sequence: left, root, right.

Edge Cases:

• An empty tree (where the root is null).

Examples

Example 1:

Input:
    1
     \
      2
     /
    3

(Root node with value 1, its right child is 2, and 2's left child is 3)

Output: [1, 3, 2]
Explanation:
1. Traverse left subtree of 1 (which is null).
2. Visit node 1. Add 1 to the result.
3. Traverse right subtree of 1.
   - Traverse left subtree of 2 (which is 3).
     - Traverse left subtree of 3 (which is null).
     - Visit node 3. Add 3 to the result.
     - Traverse right subtree of 3 (which is null).
   - Visit node 2. Add 2 to the result.
   - Traverse right subtree of 2 (which is null).

Example 2:

Input:
    5
   / \
  3   8
 / \ / \
1  4 7  9

Output: [1, 3, 4, 5, 7, 8, 9]
Explanation:
- Traverse left of 5:
  - Traverse left of 3:
    - Traverse left of 1 (null).
    - Visit 1. Result: [1]
    - Traverse right of 1 (null).
  - Visit 3. Result: [1, 3]
  - Traverse right of 3:
    - Traverse left of 4 (null).
    - Visit 4. Result: [1, 3, 4]
    - Traverse right of 4 (null).
- Visit 5. Result: [1, 3, 4, 5]
- Traverse right of 5:
  - Traverse left of 8:
    - Traverse left of 7 (null).
    - Visit 7. Result: [1, 3, 4, 5, 7]
    - Traverse right of 7 (null).
  - Visit 8. Result: [1, 3, 4, 5, 7, 8]
  - Traverse right of 8:
    - Traverse left of 9 (null).
    - Visit 9. Result: [1, 3, 4, 5, 7, 8, 9]
    - Traverse right of 9 (null).

Example 3: (Edge Case - Empty Tree)

Input:
    null

Output: []
Explanation: An empty tree has no nodes to traverse.

Constraints

• The number of nodes in the tree can be between 0 and 1000.
• The value of each node is an integer.
• The tree structure is valid (no cycles, etc.).
• The solution should aim for a time complexity of O(N), where N is the number of nodes in the tree.
• The solution should aim for a space complexity of O(H) in the best case (balanced tree) and O(N) in the worst case (skewed tree) for recursive solutions, or O(N) for iterative solutions using a stack.

Notes

• You will likely need a way to represent the tree nodes. Typically, a TreeNode structure with value, left, and right attributes (or pointers/references) is used.
• Consider both recursive and iterative approaches to solving this problem.
• For recursive solutions, think about the base case and how to combine results from sub-calls.
• For iterative solutions, a stack is a common data structure to keep track of nodes to visit.