Tree Traversal Preorder Root Left Right in DSA Java - Build from Scratch

Tree Traversal Preorder Root Left Right

📖 Scenario: Imagine you have a family tree, and you want to visit each family member starting from the oldest ancestor, then their children, and so on. This is like walking through a tree data structure in preorder: first the root, then the left branch, then the right branch.

🎯 Goal: You will build a simple binary tree and write code to traverse it in preorder (root, left, right). You will print the values of the nodes as you visit them.

📋 What You'll Learn

Create a binary tree with nodes containing integer values

Add a helper variable to hold the root node

Write a recursive method to traverse the tree in preorder (root, left, right)

Print the node values in preorder traversal order

💡 Why This Matters

🌍 Real World

Tree traversal is used in many applications like searching family trees, file systems, and organizing data hierarchically.

💼 Career

Understanding tree traversal is important for software developers working with data structures, algorithms, and coding interviews.

1

Create the binary tree nodes

Create a class called Node with an integer value and two Node references called left and right. Then create three nodes with values 1, 2, and 3. Connect the node with value 1 as root, its left child as node 2, and its right child as node 3.

DSA Java

// Define class Node and create nodes 1, 2, 3 with root connections
// Your code here

Hint

Start by defining the Node class with a constructor. Then create the root node and assign its left and right children.

2

Add a helper variable for the root node

Inside the Main class's main method, create a variable called root and assign it the node with value 1 you created earlier.

DSA Java

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        // Your code here
    }
}

Hint

The root node is the starting point of the tree. Make sure you have a variable named root assigned to the node with value 1.

3

Write the preorder traversal method

Create a static method called preorderTraversal that takes a Node parameter called node. Inside the method, if node is not null, print the node.value, then recursively call preorderTraversal on node.left, then on node.right. Call this method from main with the root node.

DSA Java

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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

        // Call preorderTraversal with root
        // Your code here
    }

    // Define preorderTraversal method
    // Your code here
}

Hint

Preorder means visit the root first, then the left subtree, then the right subtree. Use recursion to visit nodes.

4

Print the preorder traversal output

Run the program and print the preorder traversal output of the tree starting from root. The output should be the node values separated by spaces.

DSA Java

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

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

        // Print preorder traversal output
        // Your code here
    }

    public static void preorderTraversal(Node node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preorderTraversal(node.left);
            preorderTraversal(node.right);
        }
    }
}

Hint

The preorder traversal output should print the root value first, then left child, then right child separated by spaces.

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