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

Tree Traversal Inorder Left Root Right

📖 Scenario: You are working with a simple family tree where each person has a left child and a right child. You want to visit each person in a special order: first the left child, then the person themselves, and finally the right child. This order is called inorder traversal.

🎯 Goal: Build a small binary tree and write code to print the names of the people in the tree using inorder traversal (left child, root, right child).

📋 What You'll Learn

Create a class called Node with a String field name and two Node fields left and right.

Create a tree with three nodes: "Grandparent" as root, "Parent" as left child, and "Child" as right child.

Write a method called inorderTraversal that visits nodes in left-root-right order and prints their names.

Call inorderTraversal on the root node and print the names in order.

💡 Why This Matters

🌍 Real World

Tree traversal is used in many real-world applications like searching family trees, organizing files, and parsing expressions.

💼 Career

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

1

Create the Node class and tree nodes

Create a class called Node with a String field name and two Node fields called left and right. Then create three Node objects named grandparent, parent, and child with names "Grandparent", "Parent", and "Child" respectively.

DSA Java

// Your code here

Hint

Define the Node class with the fields and constructor. Then create the three nodes with the exact names and values.

2

Link the nodes to form the tree

Set the left child of grandparent to parent and the right child of grandparent to child.

DSA Java

class Node {
    String name;
    Node left;
    Node right;

    Node(String name) {
        this.name = name;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void main(String[] args) {
        Node grandparent = new Node("Grandparent");
        Node parent = new Node("Parent");
        Node child = new Node("Child");

        // Link the nodes to form the tree
        // Your code here
    }
}

Hint

Use the dot operator to set grandparent.left and grandparent.right to the correct nodes.

3

Write the inorder traversal method

Write a static method called inorderTraversal that takes a Node parameter called node. It should visit the left child by calling itself recursively, then print the name of the current node, then visit the right child by calling itself recursively. Add a check to return immediately if node is null.

DSA Java

class Node {
    String name;
    Node left;
    Node right;

    Node(String name) {
        this.name = name;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void inorderTraversal(Node node) {
        // Your code here
    }

    public static void main(String[] args) {
        Node grandparent = new Node("Grandparent");
        Node parent = new Node("Parent");
        Node child = new Node("Child");

        grandparent.left = parent;
        grandparent.right = child;
    }
}

Hint

Use recursion to visit left child, print current node's name, then visit right child. Return if node is null.

4

Call inorderTraversal and print the result

In the main method, call inorderTraversal with grandparent as the argument to print the names of the nodes in inorder sequence.

DSA Java

class Node {
    String name;
    Node left;
    Node right;

    Node(String name) {
        this.name = name;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    public static void inorderTraversal(Node node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.println(node.name);
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        Node grandparent = new Node("Grandparent");
        Node parent = new Node("Parent");
        Node child = new Node("Child");

        grandparent.left = parent;
        grandparent.right = child;

        // Call inorderTraversal with grandparent
        // Your code here
    }
}

Hint

Call inorderTraversal(grandparent); to print the names in left-root-right order.

Practice

1. What is the order of nodes visited in an inorder traversal of a binary tree?

easy

A. Left subtree, Root, Right subtree

B. Root, Left subtree, Right subtree

C. Right subtree, Root, Left subtree

D. Root, Right subtree, Left subtree

Solution

1. Step 1: Understand inorder traversal definition

   Inorder traversal visits nodes in the order: left child, then root, then right child.

2. Step 2: Apply to binary tree traversal

   This means we first visit all nodes in the left subtree, then the root node, then all nodes in the right subtree.

3. Final Answer:

   Left subtree, Root, Right subtree -> Option A

4. Quick Check:

   Inorder = Left, Root, Right [OK]

Hint: Remember: Inorder means Left, Root, then Right [OK]

Common Mistakes:

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

2. Which of the following Java method signatures correctly represents an inorder traversal of a binary tree node named root?

easy

A. void inorderTraversal(Node root) { System.out.print(root.data); inorderTraversal(root.left); inorderTraversal(root.right); }

B. void inorderTraversal(Node root) { if(root != null) { System.out.print(root.data); inorderTraversal(root.left); inorderTraversal(root.right); } }

C. void inorderTraversal(Node root) { if(root != null) { inorderTraversal(root.right); System.out.print(root.data); inorderTraversal(root.left); } }

D. void inorderTraversal(Node root) { if(root != null) { inorderTraversal(root.left); System.out.print(root.data); inorderTraversal(root.right); } }

Solution

1. Step 1: Check the order of recursive calls

   Inorder traversal visits left subtree first, then root, then right subtree.

2. Step 2: Verify method matches inorder order

   void inorderTraversal(Node root) { if(root != null) { inorderTraversal(root.left); System.out.print(root.data); inorderTraversal(root.right); } } calls inorderTraversal on left, prints root data, then calls inorderTraversal on right, matching inorder traversal.

3. Final Answer:

   Method with left call, print root, then right call -> Option D

4. Quick Check:

   Left, Root, Right order in code [OK]

Hint: Inorder method: left call, print root, right call [OK]

Common Mistakes:

• Printing root before left subtree
• Calling right subtree before left subtree
• Missing null check before recursion

3. Given the binary tree below:

    4
   / \
  2   5
 / \
1   3

What is the output of an inorder traversal?

medium

A. 1 2 3 4 5

B. 4 2 1 3 5

C. 2 1 3 4 5

D. 1 3 2 4 5

Solution

1. Step 1: Traverse left subtree of root (4)

   Left subtree is rooted at 2, which has left child 1 and right child 3. Inorder traversal of left subtree is 1, 2, 3.

2. Step 2: Visit root and right subtree

   After left subtree, visit root 4, then right subtree 5.

3. Final Answer:

   1 2 3 4 5 -> Option A

4. Quick Check:

   Inorder visits nodes in sorted order for BST [OK]

Hint: Inorder of BST gives sorted node values [OK]

Common Mistakes:

• Visiting root before left subtree
• Mixing left and right subtree order
• Skipping leaf nodes

4. Consider this Java method for inorder traversal:

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

What is the problem with this code?

medium

A. It visits nodes in preorder instead of inorder

B. It visits nodes in postorder instead of inorder

C. It visits nodes in reverse inorder (Right, Root, Left)

D. It causes a NullPointerException

Solution

1. Step 1: Analyze the recursive call order

   The method calls inorder on right subtree first, then prints root, then calls inorder on left subtree.

2. Step 2: Compare with inorder traversal definition

   Standard inorder is Left, Root, Right. This code visits Right, Root, Left, which is reverse inorder.

3. Final Answer:

   Visits nodes in reverse inorder (Right, Root, Left) -> Option C

4. Quick Check:

   Right, Root, Left order detected [OK]

Hint: Check order of recursive calls to find traversal type [OK]

Common Mistakes:

• Assuming it is correct inorder
• Ignoring order of recursive calls
• Confusing traversal types

5. You have a binary tree where each node contains a unique integer. You want to print all node values in ascending order using inorder traversal. However, the tree is not a binary search tree (BST). Which approach ensures correct ascending order output?

hard

A. Perform inorder traversal directly and print values as visited

B. Perform inorder traversal and then sort the collected values before printing

C. Perform preorder traversal and print values as visited

D. Perform postorder traversal and print values as visited

Solution

1. Step 1: Understand inorder traversal on non-BST

   Inorder traversal visits nodes in Left, Root, Right order but does not guarantee sorted order if tree is not BST.

2. Step 2: Ensure ascending order output

   To get ascending order, collect all node values during traversal, then sort them before printing.

3. Final Answer:

   Perform inorder traversal and then sort the collected values before printing -> Option B

4. Quick Check:

   Non-BST inorder not sorted; sorting needed [OK]

Hint: Inorder only sorts BST; sort after traversal for non-BST [OK]

Common Mistakes:

• Assuming inorder traversal always sorts
• Printing values during traversal without sorting
• Using preorder or postorder expecting sorted output