Solution BST Inorder Traversal

Problem Statement

Write Recursive Approach for Inorder Traversal of Binary Tree.

Given a binary tree, write a recursive algorithm to perform an inorder traversal of the tree and return the elements in the order they were visited.

Examples

Example 1:

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

Output:
Inorder Traversal: [2, 3, 4, 5, 7, 8, 9]

Explanation:
The binary tree has the following structure:
           5
         /   \
        3     8
       / \   / \
      2   4 7   9

Performing an inorder traversal visits the nodes in ascending order: 2, 3, 4, 5, 7, 8, 9.

Example 2:

Input:
           10
         /    \
        6      15
       / \    / \
      3   8  12  18
            \
             9

Output:
Inorder Traversal: [3, 6, 8, 9, 10, 12, 15, 18]

Explanation:
The binary tree has the following structure:
           10
         /    \
        6      15
       / \    / \
      3   8  12  18
            \
             9

Performing an inorder traversal visits the nodes in ascending order: 3, 6, 8, 9, 10, 12, 15, 18.

Example 3:

Input:
           20
         /    \
        12     25
       / \    / \
      8   15  22  28
     / \       \
    6   10      24

Output:
Inorder Traversal: [6, 8, 10, 12, 15, 20, 22, 24, 25, 28]

Explanation:
The binary tree has the following structure:
           20
         /    \
        12     25
       / \    / \
      8   15  22  28
     / \       \
    6   10      24

Performing an inorder traversal visits the nodes in ascending order: 6, 8, 10, 12, 15, 20, 22, 24, 25, 28.

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution

The inorder traversal of a binary tree follows a recursive approach. We can define the algorithm as follows:

1. Base Case: If the current node is null, return.
2. Recursive Case:
   • Recursively traverse the left subtree.
   • Visit the current node.
   • Recursively traverse the right subtree.

By following this approach, we can perform an inorder traversal of the binary tree.

Code

Here is the code for this algorithm:

import java.util.*;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int val) {
//         this.val = val;
//     }
// }

class Solution {

  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
  }

  private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) {
      return; // Base case: reached the end of the subtree
    }

    inorder(node.left, result); // Recursively traverse the left subtree
    result.add(node.val); // Visit the current node
    inorder(node.right, result); // Recursively traverse the right subtree
  }

  public static void main(String[] args) {
    // Example inputs
    TreeNode root = new TreeNode(1);
    root.right = new TreeNode(2);
    root.right.left = new TreeNode(3);

    Solution inorderTraversal = new Solution();
    List<Integer> result = inorderTraversal.inorderTraversal(root);

    System.out.println("Inorder Traversal: " + result);
  }
}

Time and Space Complexity

The time complexity of the algorithm is , where n is the number of nodes in the binary tree. This is because we need to visit each node exactly once.

The space complexity of the algorithm is , where h is the height of the binary tree. In the worst case, where the binary tree is skewed (i.e., a linked list), the height h is equal to the number of nodes, resulting in space complexity. However, in a balanced binary tree, the height h is logarithmic to the number of nodes, resulting in efficient space usage with space complexity.

I'm working on the problem **Solution BST Inorder Traversal** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Solution BST Inorder Traversal** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Solution BST Inorder Traversal**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Solution BST Inorder Traversal**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.