Tree Traversal Inorder Left Root Right in DSA Typescript

Mental Model

Visit the left side first, then the middle, then the right side to see all parts in order.

Analogy: Like reading a book where you first look at the left page, then the middle page, then the right page in order.

    2
   / \
  1   3
↑root

Dry Run Walkthrough

Input: Tree: root=2, left=1, right=3

Goal: Print nodes in order: left child, root, right child

Step 1: Go left from root 2 to node 1

    2
   / \
  [1] 3
↑curr at 1

Why: We visit left child first in inorder

Step 2: Visit node 1 (no left child)

1 visited
    2
   / \
  1   3
↑curr back to 2

Why: Left subtree done, now visit root

Step 3: Visit root node 2

1 -> 2 visited
    2
   / \
  1   3
↑curr moves right to 3

Why: After root, visit right child

Step 4: Visit right child node 3

1 -> 2 -> 3 visited
    2
   / \
  1   3
Traversal complete

Why: Right subtree visited last

Result:

1 -> 2 -> 3

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function inorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];
  function traverse(node: TreeNode | null) {
    if (node === null) return; // base case: no node
    traverse(node.left); // visit left subtree
    result.push(node.val); // visit root
    traverse(node.right); // visit right subtree
  }
  traverse(root);
  return result;
}

// Driver code
const root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
const output = inorderTraversal(root);
console.log(output.join(' -> '));

if (node === null) return; // base case: no node

stop recursion when no node

traverse(node.left); // visit left subtree

go left first to visit left subtree

result.push(node.val); // visit root

add current node value after left subtree

traverse(node.right); // visit right subtree

go right last to visit right subtree

Output

1 -> 2 -> 3

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(n) due to recursion stack and output array storing all nodes

vs Alternative: Compared to preorder or postorder, inorder also visits all nodes once, so same time complexity; space depends on tree height for recursion

Edge Cases

empty tree (root is null)

returns empty list without error

DSA Typescript

if (node === null) return; // base case: no node

single node tree

returns list with single node value

DSA Typescript

if (node === null) return; // base case: no node

When to Use This Pattern

When you need to visit nodes in sorted order for a binary search tree, use inorder traversal because it visits left, root, then right.

Common Mistakes

Mistake: Visiting root before left subtree (preorder) instead of after
Fix: Call traverse(node.left) before pushing node.val

Mistake: Visiting right subtree before root
Fix: Push node.val before calling traverse(node.right)

Summary

Visits nodes in left-root-right order to get sorted sequence in BST

Use when you want to process nodes in ascending order

Remember: left subtree first, then root, then right subtree