Binary Tree Inorder Traversal

Problem Statement

You’re a tree whisperer exploring a binary tree. Your mission: traverse it inorder—left subtree, root, right subtree—and return the node values in that sequence. This easy-level classic is a dance through branches—master recursion or iteration to unlock its secrets!

Example

Input: root = [1,null,2,3]

Tree:

   1
    \
     2
    /
   3

Output: [1, 3, 2] (Left: 1, Right: 3, Root: 2)

Input: root = []

Output: [] (Empty tree)

Input: root = [1,2,3,4,5]

Tree:

   1
  / \
 2   3
/ \
4  5

Output: [4, 2, 5, 1, 3]

Code

class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        Stack stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        return result;
    }
}
            

class Solution:
    def inorderTraversal(self, root):
        result, stack = [], []
        curr = root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            result.append(curr.val)
            curr = curr.right
        return result
            

function inorderTraversal(root) {
    let result = [], stack = [];
    let curr = root;
    while (curr || stack.length) {
        while (curr) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.push(curr.val);
        curr = curr.right;
    }
    return result;
}
            

Explanation

• Traversal Insight: Inorder = Left, Root, Right—perfect for BST sorted order.
• Iterative Flow: Use a stack to mimic recursion: push all left nodes, pop, process, move right.
• Example Walkthrough: [1,null,2,3] → stack=[1,2], pop 1 (add 1), pop 2 (add 3,2) → [1,3,2].
• Recursive Alt:

  def inorder(root):
      return inorder(root.left) + [root.val] + inorder(root.right) if root else []

• Edge Cases: Empty tree, single node, skewed tree—all handled seamlessly.

Note