Tree Traversal Preorder Root Left Right in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Preorder Traversal on a Simple Tree

What is the output of the preorder traversal (Root, Left, Right) of the following binary tree?

Tree structure:
1
/ \ 2 3
/
4

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class Main {
    public static void preorder(Node root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        preorder(root);
    }
}

A 1 2 4 3

B 1 3 2 4

C 4 2 1 3

D 2 4 1 3

💡 Hint

Remember preorder means visit root first, then left subtree, then right subtree.

Preorder traversal visits nodes in the order: root, left child, right child. Starting at 1, then left subtree 2 and its left child 4, then right subtree 3.

❓ Predict Output

intermediate

Preorder Traversal Output with Null Children

What will be printed by the preorder traversal of this tree?

Tree structure:
5
\ 6
/
7

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class Main {
    public static void preorder(Node root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        root.right = new Node(6);
        root.right.left = new Node(7);
        preorder(root);
    }
}

A 7 6 5

B 5 7 6

C 5 6 7

D 6 7 5

💡 Hint

Preorder visits root first, then left, then right.

Start at 5, then left child is null so skip, then right child 6, then 6's left child 7.

🔧 Debug

advanced

Identify the Error in Preorder Traversal Code

What error will this code produce when running preorder traversal on a non-empty tree?

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class Main {
    public static void preorder(Node root) {
        if (root == null) return;
        preorder(root.left);
        System.out.print(root.val + " ");
        preorder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        preorder(root);
    }
}

A The code will cause a NullPointerException

B The output will be: 20 10 30

C The output will be: 10 20 30

D The output will be: 10 30 20

💡 Hint

Check the order of printing and recursive calls.

The code prints after visiting left subtree, so it is an inorder traversal, not preorder. Output is left, root, right: 20 10 30.

❓ Predict Output

advanced

Preorder Traversal Output of a Larger Tree

What is the preorder traversal output of this tree?

Tree structure:
8
/ \ 3 10
/ \ \ 1 6 14
/ \ / 4 7 13

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int v) { val = v; left = right = null; }
}

public class Main {
    public static void preorder(Node root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(8);
        root.left = new Node(3);
        root.right = new Node(10);
        root.left.left = new Node(1);
        root.left.right = new Node(6);
        root.left.right.left = new Node(4);
        root.left.right.right = new Node(7);
        root.right.right = new Node(14);
        root.right.right.left = new Node(13);
        preorder(root);
    }
}

A 8 3 6 1 4 7 10 14 13

B 8 10 14 13 3 6 4 7 1

C 1 3 4 6 7 8 10 13 14

D 8 3 1 6 4 7 10 14 13

💡 Hint

Remember preorder visits root first, then left subtree, then right subtree.

Start at 8, then left subtree 3, then 3's left 1, then 3's right 6 and its children 4 and 7, then right subtree 10, then 10's right 14 and its left 13.

🧠 Conceptual

expert

Number of Nodes Visited in Preorder Traversal

Given a binary tree with 15 nodes, how many nodes will be visited during a complete preorder traversal?

A 15

B 30

C 14

D 7

💡 Hint

Preorder traversal visits every node exactly once.

Preorder traversal visits every node in the tree exactly once, so all 15 nodes are visited.

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