Tree Traversal Preorder Root Left Right in DSA Java

Mental Model

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

Analogy: Imagine reading a book where you first look at the title page (root), then read the left page (left subtree), and then the right page (right subtree).

    1
   / \
  2   3
 / \
4   5

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

Output: 1

Why: Start traversal at the root

Step 2: Traverse left subtree starting at node 2

Output: 1 2

Why: After root, visit left subtree root

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

Output: 1 2 4

Why: Visit left child before right child

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

Output: 1 2 4 5

Why: After left subtree, visit right subtree

Step 5: Traverse right subtree starting at node 3

Output: 1 2 4 5 3

Why: Finally visit right subtree of root

Result:

Output: 1 2 4 5 3

Annotated Code

DSA Java

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

public class PreorderTraversal {
    public static void preorder(TreeNode root) {
        if (root == null) return; // base case: no node
        System.out.print(root.val + " "); // visit root first
        preorder(root.left); // traverse left subtree
        preorder(root.right); // traverse right subtree
    }

    public static void main(String[] args) {
        TreeNode 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);

        preorder(root); // expected output: 1 2 4 5 3
    }
}

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

stop recursion when no node to visit

System.out.print(root.val + " "); // visit root first

visit current node before children

preorder(root.left); // traverse left subtree

recursively visit left subtree

preorder(root.right); // traverse right subtree

recursively visit right subtree

Output

1 2 4 5 3 

Complexity Analysis

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

Space: O(h) where h is the height of the tree due to recursion stack

vs Alternative: Compared to iterative traversal, recursive preorder is simpler but uses call stack; iterative uses explicit stack but can be more complex

Edge Cases

Empty tree (root is null)

No output, function returns immediately

DSA Java

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

Tree with single node

Only root node value is printed

DSA Java

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

Tree with only left children

Nodes printed in root-left order down the chain

DSA Java

preorder(root.left); // traverse left subtree

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 and right children before the root node
Fix: Print the root node value before recursive calls to left and right children

Summary

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

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

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

Practice

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

easy

A. Left, Root, Right

B. Right, Root, Left

C. Left, Right, Root

D. Root, Left, Right

Solution

1. Step 1: Understand preorder traversal definition

   Preorder traversal visits the root node first, then the left subtree, and finally the right subtree.

2. Step 2: Match the order with options

   Root, Left, Right matches the order Root, Left, Right exactly.

3. Final Answer:

   Root, Left, Right -> Option D

4. Quick Check:

   Preorder = Root, Left, Right [OK]

Hint: Remember preorder starts with the root node first [OK]

Common Mistakes:

• Confusing preorder with inorder or postorder
• Visiting left before root
• Visiting right before left

2. Which of the following Java method signatures correctly represents a preorder traversal method for a binary tree node class named Node?

easy

A. void preorderTraversal(Node root) {}

B. int preorderTraversal(Node root) {}

C. Node preorderTraversal() {}

D. void preorderTraversal() {}

Solution

1. Step 1: Identify correct method signature for preorder traversal

   Preorder traversal usually returns void and takes the root node as input to traverse the tree.

2. Step 2: Check options for matching signature

   void preorderTraversal(Node root) {} matches void return type and takes Node root as parameter, which is correct.

3. Final Answer:

   void preorderTraversal(Node root) {} -> Option A

4. Quick Check:

   Traversal method is void and takes root node [OK]

Hint: Traversal methods usually return void and take root node [OK]

Common Mistakes:

• Using return type int instead of void
• Not passing root node as parameter
• Returning Node instead of void

3. Given the following binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a preorder traversal?

medium

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

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

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

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

Solution

1. Step 1: Start preorder traversal at root node 1

   Visit 1 first, then move to left subtree.

2. Step 2: Traverse left subtree of 1: nodes 2, 4, 5

   Visit 2, then 4 (left child), then 5 (right child).

3. Step 3: Traverse right subtree of 1: node 3

   Visit 3 last.

4. Final Answer:

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

5. Quick Check:

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

Hint: Follow Root, then left subtree, then right subtree order [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder
• Visiting right subtree before left
• Skipping leaf nodes

4. Consider this Java preorder traversal method for a binary tree node class Node:

void preorder(Node root) {
  if (root == null) return;
  preorder(root.left);
  System.out.print(root.data + " ");
  preorder(root.right);
}

What is the error in this code?

medium

A. It prints nodes in inorder, not preorder

B. It causes a NullPointerException

C. It misses the right subtree

D. It prints nodes in postorder

Solution

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

   The method first recursively visits left subtree, then prints root data, then visits right subtree.

2. Step 2: Compare with preorder definition

   Preorder should print root first, but this code prints root after left subtree, which is inorder traversal.

3. Final Answer:

   It prints nodes in inorder, not preorder -> Option A

4. Quick Check:

   Print before left recursion for preorder [OK]

Hint: Print root before recursive calls for preorder [OK]

Common Mistakes:

• Printing after left subtree instead of before
• Confusing preorder with inorder
• Missing base case for null

5. You want to collect all node values of a binary tree in preorder traversal into a list in Java. Which code snippet correctly does this?

hard

A. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.left, list);
list.add(root.data);
preorder(root.right, list);
}

B. void preorder(Node root, List<Integer> list) {
if (root == null) return;
list.add(root.data);
preorder(root.left, list);
preorder(root.right, list);
}

C. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.left, list);
preorder(root.right, list);
list.add(root.data);
}

D. void preorder(Node root, List<Integer> list) {
if (root == null) return;
preorder(root.right, list);
list.add(root.data);
preorder(root.left, list);
}

Solution

1. Step 1: Understand preorder traversal order

   Preorder visits root first, then left subtree, then right subtree.

2. Step 2: Check which code adds root data before recursive calls

   void preorder(Node root, List<Integer> list) { if (root == null) return; list.add(root.data); preorder(root.left, list); preorder(root.right, list); } adds root.data to list first, then recursively visits left and right subtrees, matching preorder.

3. Final Answer:

   void preorder(Node root, List<Integer> list) { if (root == null) return; list.add(root.data); preorder(root.left, list); preorder(root.right, list); } -> Option B

4. Quick Check:

   Add root before left and right recursion [OK]

Hint: Add root data before recursive calls for preorder list [OK]

Common Mistakes:

• Adding node data after left subtree (inorder)
• Adding node data after both subtrees (postorder)
• Visiting right subtree before left