Tree Traversal Preorder Root Left Right in DSA Javascript

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 as root, 2 as left child, 3 as right child, 4 as left child of 2, 5 as right child of 2

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 root

Step 2: Traverse left subtree starting at node 2

Visited: 1 -> 2

Why: After root, visit 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: Back to node 2, traverse right subtree, visit node 5

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

Why: Complete left subtree before right subtree

Step 5: Traverse right subtree starting at node 3

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

Why: After left subtree, visit right subtree

Result:

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

Annotated Code

DSA Javascript

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

function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (node === null) return; // base case: no node
    result.push(node.val); // visit root
    traverse(node.left); // traverse left subtree
    traverse(node.right); // traverse right subtree
  }
  traverse(root);
  return result.join(' -> ');
}

// Build tree from dry_run input
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);

console.log(preorderTraversal(root));

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

stop traversal when no node to visit

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

record current node value before children

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

explore left subtree first

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

explore right subtree after left

Output

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

Complexity Analysis

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

Space: O(n) due to recursion stack and result storage in worst case

vs Alternative: Compared to inorder or postorder, preorder visits nodes in a different order but has the same time and space complexity

Edge Cases

Empty tree (root is null)

Returns empty string, no nodes visited

DSA Javascript

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

Tree with single node

Returns that single node value

DSA Javascript

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

When to Use This Pattern

When you need to process or print nodes starting from the root before children, preorder traversal is the pattern to use.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Always visit the current node first before traversing children

Mistake: Not handling null nodes causing errors
Fix: Add base case to return immediately when node is null

Summary

Visits nodes starting from root, then left subtree, then right subtree

Use when you want to process root before its children, such as copying a tree

Remember: root first, then left, then right