Tree Traversal Inorder Left Root Right in DSA Javascript

Mental Model

Visit the left side first, then the middle, then the right side in a tree.

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

    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 subtree first in inorder

Step 2: Visit node 1 (no left child)

Visited: 1
    2
   / \
  1  3
↑curr back to 2

Why: Left subtree done, now visit root

Step 3: Visit root node 2

Visited: 1 2
    2
   / \
  1  3
↑curr moves right

Why: After root, visit right subtree

Step 4: Go right from root 2 to node 3

    2
   / \
  1  [3]
↑curr at 3

Why: Visit right child last

Step 5: Visit node 3 (no children)

Visited: 1 2 3
    2
   / \
  1  3
Traversal complete

Why: All nodes visited in left-root-right order

Result:

1 -> 2 -> 3 -> null

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function inorderTraversal(root) {
  const result = [];
  function traverse(node) {
    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(' -> ') + ' -> null');

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 -> null

Complexity Analysis

Time: O(n) because we visit each node 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 and space complexity

Edge Cases

Empty tree (root is null)

Returns empty list, no nodes to visit

DSA Javascript

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

Single node tree

Returns list with single node value

DSA Javascript

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

Tree with only left children

Visits nodes from leftmost up to root in order

DSA Javascript

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

When to Use This Pattern

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

Common Mistakes

Mistake: Visiting root before left subtree (preorder) instead of after
Fix: Change order to traverse left subtree first, then root, then right subtree

Mistake: Forgetting to check for null node and causing errors
Fix: Add base case to return immediately if node is null

Summary

Visits tree nodes in left-root-right order.

Use when you want nodes in sorted order from a binary search tree.

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