Tree Traversal Preorder Root Left Right in DSA Typescript

Mental Model

Visit the root node first, then explore the left subtree, and finally the right subtree.

Analogy: Imagine reading a family tree starting from the oldest ancestor, then visiting their left child and all descendants before moving to the right child and their descendants.

    1
   / \
  2   3
 / \
4   5

↑ Root at 1

Dry Run Walkthrough

Input: Tree: 1 (root) with left child 2 and right child 3; 2 has children 4 (left) and 5 (right)

Goal: Print nodes in preorder: root first, then left subtree, then right subtree

Step 1: Visit root node 1

Visited: 1

Why: Start traversal at the root

Step 2: Traverse left subtree starting at node 2

Visited: 1 -> 2

Why: After root, preorder visits left subtree

Step 3: Traverse left subtree of node 2, visit node 4

Visited: 1 -> 2 -> 4

Why: Preorder visits left child before right

Step 4: Traverse right subtree of node 2, visit node 5

Visited: 1 -> 2 -> 4 -> 5

Why: After left subtree, visit right subtree

Step 5: Traverse right subtree starting at node 3

Visited: 1 -> 2 -> 4 -> 5 -> 3

Why: Finally visit right subtree of root

Result:

Visited nodes in order: 1 -> 2 -> 4 -> 5 -> 3

Annotated Code

DSA Typescript

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

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

// Driver code
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const traversalResult = preorderTraversal(root);
console.log(traversalResult.join(' -> ') + ' -> null');

if (root === null) return result;

stop recursion when no node to visit

result.push(root.val);

visit current node first

preorderTraversal(root.left, result);

recursively traverse left subtree

preorderTraversal(root.right, result);

recursively traverse right subtree

Output

1 -> 2 -> 4 -> 5 -> 3 -> null

Complexity Analysis

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

Space: O(n) due to recursion stack in worst case (skewed tree) and output storage

vs Alternative: Compared to inorder or postorder, preorder visits nodes in a different order but all have O(n) time; iterative versions may use explicit stack instead of recursion

Edge Cases

Empty tree (root is null)

Returns empty traversal result without error

DSA Typescript

if (root === null) return result;

Single node tree

Returns list with only that node's value

DSA Typescript

result.push(root.val);

Tree with only left children

Visits nodes top-down along left branch correctly

DSA Typescript

preorderTraversal(root.left, result);

When to Use This Pattern

When you need to process the root node before its children in a tree, use preorder traversal to visit nodes in root-left-right order.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Always push the root node's value before recursive calls to children

Mistake: Forgetting to check for null nodes before recursion
Fix: Add base case to return when node is null

Summary

Visits nodes in order: root, then left subtree, then right subtree.

Use when you want to process the root before its children, such as copying a tree or prefix expression evaluation.

The key is to visit the current node first, then recursively visit left and right children.