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

Tree Traversal Postorder Left Right Root

📖 Scenario: You are working with a simple family tree where each person can have up to two children. You want to visit all family members in a special order: first the left child, then the right child, and finally the parent. This order is called postorder traversal.

🎯 Goal: Build a Java program that creates a small binary tree, sets up a method to traverse it in postorder (left, right, root), and prints the names of the family members in that order.

📋 What You'll Learn

Create a binary tree with nodes containing String names

Implement postorder traversal method using recursion

Print the names in postorder sequence

💡 Why This Matters

🌍 Real World

Tree traversal is used in many real-world applications like file system navigation, expression evaluation, and organizing hierarchical data.

💼 Career

Understanding tree traversal is essential for software developers working with data structures, algorithms, and systems that manage hierarchical information.

1

Create the Tree Node Class and Root Node

Create a class called TreeNode with a String field called name, and two TreeNode fields called left and right. Then create a TreeNode variable called root and set it to a new TreeNode with the name "Grandparent".

DSA Java

// Define TreeNode class and create root node named "Grandparent"
// Your code here

Hint

Start by defining the TreeNode class with the required fields and constructor. Then create the root node inside the main method.

2

Add Left and Right Children to the Root

Add two children to the root node: set root.left to a new TreeNode with the name "Parent1" and root.right to a new TreeNode with the name "Parent2".

DSA Java

class TreeNode {
    String name;
    TreeNode left;
    TreeNode right;

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

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("Grandparent");
        // Add left and right children to root
        // Your code here
    }
}

Hint

Use the root.left and root.right fields to assign new TreeNode objects with the given names.

3

Write the Postorder Traversal Method

Write a static method called postorderTraversal that takes a TreeNode parameter called node. The method should recursively visit the left child, then the right child, and then print the name of the current node. Use System.out.println(node.name) to print the name.

DSA Java

class TreeNode {
    String name;
    TreeNode left;
    TreeNode right;

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

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("Grandparent");
        root.left = new TreeNode("Parent1");
        root.right = new TreeNode("Parent2");
    }

    // Write postorderTraversal method below
    // Your code here
}

Hint

Use recursion to visit left and right children before printing the current node's name.

4

Call Postorder Traversal and Print Output

In the main method, call postorderTraversal(root) to print the names of the nodes in postorder sequence.

DSA Java

class TreeNode {
    String name;
    TreeNode left;
    TreeNode right;

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

public class Main {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("Grandparent");
        root.left = new TreeNode("Parent1");
        root.right = new TreeNode("Parent2");
        // Call postorderTraversal to print names
        // Your code here
    }

    public static void postorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.println(node.name);
    }
}

Hint

Call postorderTraversal(root) inside main to print the names in postorder.

Practice

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

easy

A. Root node, Left subtree, Right subtree

B. Left subtree, Right subtree, Root node

C. Root node, Right subtree, Left subtree

D. Right subtree, Left subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits nodes in the order: left subtree first, then right subtree, and finally the root node.

2. Step 2: Match the order with options

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

3. Final Answer:

   Left subtree, Right subtree, Root node -> Option B

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember: postorder ends with root after children [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Visiting root before children
• Swapping left and right subtree order

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

easy

A. void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); }

B. void postorder(Node root) { visit(root); postorder(root.left); postorder(root.right); }

C. void postorder(Node root) { postorder(root.right); postorder(root.left); visit(root); }

D. void postorder(Node root) { visit(root.left); visit(root.right); visit(root); }

Solution

1. Step 1: Recall postorder traversal steps

   Postorder visits left subtree, then right subtree, then root node (visit).

2. Step 2: Check each method's order

   void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } calls postorder on left, then right, then visits root, matching postorder correctly.

3. Final Answer:

   void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } -> Option A

4. Quick Check:

   Left, Right, Root method order = void postorder(Node root) { postorder(root.left); postorder(root.right); visit(root); } [OK]

Hint: Postorder calls left, right, then visit root [OK]

Common Mistakes:

• Visiting root before children
• Swapping left and right recursive calls
• Using visit instead of recursive call for children

3. Given the binary tree below:

    1
   / \
  2   3
 / \
4   5

What is the output of the postorder traversal?

medium

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

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

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

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

Solution

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

   Left subtree rooted at 2: postorder visits 4 (left), 5 (right), then 2 (root) -> [4, 5, 2]

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), so visit 3, then visit root 1 -> [3, 1]

3. Step 3: Combine all parts

   Full postorder: left subtree [4,5,2], right subtree [3], root [1] -> [4, 5, 2, 3, 1]

4. Final Answer:

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

5. Quick Check:

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

Hint: Visit left subtree fully, then right, then root last [OK]

Common Mistakes:

• Visiting root before children
• Mixing up left and right subtree order
• Outputting preorder or inorder instead

4. Consider this Java method for postorder traversal:

void postorder(Node root) {
  if (root == null) return;
  postorder(root.right);
  postorder(root.left);
  visit(root);
}

What is the main problem with this code?

medium

A. It visits right subtree before left subtree, reversing order

B. It causes infinite recursion

C. It visits the root before children

D. It does not check for null root

Solution

1. Step 1: Analyze traversal order in code

   The code calls postorder on right subtree first, then left subtree, then visits root.

2. Step 2: Compare with correct postorder order

   Correct postorder is left, right, root. This code reverses left and right subtree order.

3. Final Answer:

   It visits right subtree before left subtree, reversing order -> Option A

4. Quick Check:

   Left before right needed, code does right before left [OK]

Hint: Left subtree must be visited before right in postorder [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Ignoring null check (though present here)
• Visiting root before children

5. You want to collect all node values of a binary tree in postorder traversal into a list. Which of the following Java code snippets correctly implements this?

hard

A. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); result.add(root.val); postorder(root.right, result); }

B. void postorder(Node root, List<Integer> result) { if(root==null) return; result.add(root.val); postorder(root.left, result); postorder(root.right, result); }

C. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.right, result); postorder(root.left, result); result.add(root.val); }

D. void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); }

Solution

1. Step 1: Understand postorder traversal with list collection

   Postorder visits left subtree, then right subtree, then adds root value to list.

2. Step 2: Check each code snippet's order

   void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } calls postorder on left, then right, then adds root value last, matching postorder correctly.

3. Final Answer:

   void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } -> Option D

4. Quick Check:

   Left, Right, Root with result.add last = void postorder(Node root, List<Integer> result) { if(root==null) return; postorder(root.left, result); postorder(root.right, result); result.add(root.val); } [OK]

Hint: Add root value after left and right recursive calls [OK]

Common Mistakes:

• Adding root value before children
• Swapping left and right subtree calls
• Forgetting null check before recursion