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.

Practice

1. What is the order of nodes visited in a preorder tree traversal?

easy

A. Root, Left, Right

B. Left, Root, Right

C. Left, Right, Root

D. Right, Left, Root

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then recursively visits the left subtree, followed by the right subtree.

2. Step 2: Match the order with options

   The order Root, Left, Right matches the preorder traversal definition exactly.

3. Final Answer:

   Root, Left, Right -> Option A

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Preorder always starts with the root node first [OK]

Common Mistakes:

• Confusing preorder with inorder or postorder
• Visiting left or right before root
• Mixing up traversal orders

2. Which of the following TypeScript function signatures correctly represents a preorder traversal function for a binary tree node?

easy

A. function preorder(node: TreeNode): number[]

B. function preorder(node: TreeNode | null): void

C. function preorder(): TreeNode

D. function preorder(node: TreeNode, result: number[]): number

Solution

1. Step 1: Analyze function parameters and return type

   A preorder traversal function typically takes a node (or null) and returns void if it prints or processes nodes directly.

2. Step 2: Check each option

   function preorder(node: TreeNode | null): void accepts a node or null and returns void, which fits a traversal that processes nodes without returning a value.

3. Final Answer:

   function preorder(node: TreeNode | null): void -> Option B

4. Quick Check:

   Traversal function signature with node or null and void return [OK]

Hint: Traversal functions usually take a node and return void or array [OK]

Common Mistakes:

• Missing null in node parameter type
• Wrong return type for traversal
• Incorrect number of parameters

3. Given the following binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a preorder traversal (Root, Left, Right)?

medium

A. [4, 2, 5, 1, 3]

B. [2, 4, 5, 1, 3]

C. [1, 2, 4, 5, 3]

D. [1, 3, 2, 4, 5]

Solution

1. Step 1: Start at root node 1

   Preorder visits root first: 1

2. Step 2: Traverse left subtree of 1

   Visit node 2, then its left child 4, then right child 5: 2, 4, 5

3. Step 3: Traverse right subtree of 1

   Visit node 3: 3

4. Final Answer:

   [1, 2, 4, 5, 3] -> Option C

5. Quick Check:

   Preorder = Root, Left, Right = [1, 2, 4, 5, 3] [OK]

Hint: Visit root first, then left subtree, then right subtree [OK]

Common Mistakes:

• Visiting left subtree after right subtree
• Starting traversal from left child instead of root
• Mixing preorder with inorder or postorder

4. Consider this TypeScript preorder traversal function:

function preorder(node: TreeNode | null): void {
  if (node === null) return;
  preorder(node.left);
  console.log(node.val);
  preorder(node.right);
}

What is the error in this code?

medium

A. It does not handle null nodes

B. It will cause infinite recursion

C. It prints nodes in postorder

D. It visits nodes in inorder, not preorder

Solution

1. Step 1: Analyze the order of operations in the function

   The function first calls preorder on left child, then prints current node, then calls preorder on right child.

2. Step 2: Compare with preorder definition

   Preorder should print the node first, then traverse left and right. This code prints after left subtree, so it is inorder traversal.

3. Final Answer:

   It visits nodes in inorder, not preorder -> Option D

4. Quick Check:

   Print before recursive calls = preorder; here print is in middle [OK]

Hint: Print node value before recursive calls for preorder [OK]

Common Mistakes:

• Printing node after left subtree instead of before
• Confusing traversal orders
• Missing base case for null

5. You want to collect all node values of a binary tree in preorder traversal into an array. Which TypeScript function correctly implements this?

hard

A. function preorder(node: TreeNode | null, result: number[] = []): number[] {
if (!node) return result;
result.push(node.val);
preorder(node.left, result);
preorder(node.right, result);
return result;
}

B. function preorder(node: TreeNode | null): number[] {
if (!node) return [];
return [...preorder(node.left), node.val, ...preorder(node.right)];
}

C. function preorder(node: TreeNode | null): number[] {
if (!node) return [];
return [...preorder(node.left), ...preorder(node.right), node.val];
}

D. function preorder(node: TreeNode | null): number[] {
if (!node) return [];
return [node.val, ...preorder(node.right), ...preorder(node.left)];
}

Solution

1. Step 1: Understand preorder traversal collection

   Preorder visits root first, then left subtree, then right subtree, collecting values in order.

2. Step 2: Check each function's order and correctness

   function preorder(node: TreeNode | null, result: number[] = []): number[] { if (!node) return result; result.push(node.val); preorder(node.left, result); preorder(node.right, result); return result; } pushes node.val first, then recursively collects left and right, returning the result array correctly.

3. Final Answer:

   function preorder(node: TreeNode | null, result: number[] = []): number[] { if (!node) return result; result.push(node.val); preorder(node.left, result); preorder(node.right, result); return result; } -> Option A

4. Quick Check:

   Push root first, then left and right recursively [OK]

Hint: Push root value before recursive calls to left and right [OK]

Common Mistakes:

• Collecting left subtree before root
• Mixing left and right subtree order
• Returning new arrays instead of accumulating