Why BST Over Plain Binary Tree in DSA Java - See It Work

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of books and you want to organize them so you can find any book quickly. You can stack them randomly or arrange them in a special order. This project shows why arranging books in a special order (like a Binary Search Tree) helps you find books faster than just stacking them randomly (like a plain Binary Tree).

🎯 Goal: You will create a simple binary tree and a binary search tree (BST) with the same values. Then, you will see how searching for a value works differently in both. This will help you understand why BSTs are better for quick searching.

📋 What You'll Learn

Create a plain binary tree with nodes containing integer values

Create a binary search tree (BST) with the same integer values

Write a method to search for a value in the plain binary tree

Write a method to search for a value in the BST

Print the search results for a given value from both trees

💡 Why This Matters

🌍 Real World

Organizing data so it can be found quickly is important in many apps like phone contacts, file systems, and databases. BSTs help keep data sorted and easy to search.

💼 Career

Understanding BSTs is key for software developers working with data storage, search engines, and performance optimization.

1

Create a Plain Binary Tree

Create a class called Node with an integer value, and two Node references called left and right. Then create a plain binary tree with root node value 10, left child 5, and right child 15.

DSA Java

// Define Node class and create plain binary tree root with left and right children
// Your code here

Hint

Start by defining the Node class with the required fields. Then create the root and its children as new Node objects.

2

Create a Binary Search Tree (BST)

Add a method called insert in the Main class that inserts values into the BST following BST rules. Then create a BST root node with value 10 and insert values 5 and 15 using the insert method.

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 {
    // Add insert method here

    public static void main(String[] args) {
        Node root = new Node(10);
        root = insert(root, 5);
        root = insert(root, 15);
    }
}

Hint

Write a recursive insert method that places smaller values to the left and larger values to the right. Use it to build the BST.

3

Write Search Methods for Both Trees

Write a method called searchPlain that searches for a value in the plain binary tree by checking nodes in any order (left then right). Also write a method called searchBST that searches for a value in the BST using BST rules (go left if smaller, right if larger). Both methods return true if found, false otherwise.

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 Node insert(Node root, int value) {
        if (root == null) {
            return new Node(value);
        }
        if (value  root.value) {
            root.right = insert(root.right, value);
        }
        return root;
    }

    // Add searchPlain method here
    // Add searchBST method here

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root = insert(root, 5);
        root = insert(root, 15);
    }
}

Hint

Use recursion to check nodes in the plain tree without order. For BST, use the value comparison to decide which side to search.

4

Print Search Results for Value 15

Print the results of searching for the value 15 in both the plain binary tree and the BST using searchPlain and searchBST methods. Use System.out.println to print "Found in plain tree: true/false" and "Found in BST: true/false".

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 Node insert(Node root, int value) {
        if (root == null) {
            return new Node(value);
        }
        if (value  root.value) {
            root.right = insert(root.right, value);
        }
        return root;
    }

    public static boolean searchPlain(Node root, int value) {
        if (root == null) {
            return false;
        }
        if (root.value == value) {
            return true;
        }
        return searchPlain(root.left, value) || searchPlain(root.right, value);
    }

    public static boolean searchBST(Node root, int value) {
        if (root == null) {
            return false;
        }
        if (root.value == value) {
            return true;
        } else if (value < root.value) {
            return searchBST(root.left, value);
        } else {
            return searchBST(root.right, value);
        }
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root = insert(root, 5);
        root = insert(root, 15);

        // Print search results for value 15
        // Your code here
    }
}

Hint

Use System.out.println to print the results of searchPlain(root, 15) and searchBST(root, 15).

Practice

1. Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching elements?

easy

A. Because BST does not require pointers to child nodes

B. Because BST uses less memory than a plain Binary Tree

C. Because BST nodes can have more than two children

D. Because BST keeps elements in sorted order allowing faster search

Solution

1. Step 1: Understand the structure difference

   A plain Binary Tree has no order, so searching requires checking many nodes. BST keeps nodes sorted so left child is smaller and right child is larger.

2. Step 2: Analyze search efficiency

   Because of sorting, BST allows searching by comparing and moving left or right, reducing search time to O(log n) on average, unlike plain Binary Tree which can be O(n).

3. Final Answer:

   Because BST keeps elements in sorted order allowing faster search -> Option D

4. Quick Check:

   Sorted structure = faster search [OK]

Hint: BST is sorted, so search is faster than plain tree [OK]

Common Mistakes:

• Thinking BST uses less memory
• Confusing number of children per node
• Assuming BST has no pointers

2. Which of the following is the correct way to declare a node class for a BST in Java?

easy

A. class Node { int data; Node left; Node right; }

B. class Node { int data; Node left, right; void insert(int val); }

C. class Node { int data; Node left; Node right; Node parent; }

D. class Node { int data; Node left; Node right; int height; }

Solution

1. Step 1: Identify minimal BST node structure

   A BST node must store data and references to left and right child nodes. class Node { int data; Node left; Node right; } shows this minimal structure.

2. Step 2: Check other options for extra or missing parts

   class Node { int data; Node left, right; void insert(int val); } adds a method which is not part of declaration only. class Node { int data; Node left; Node right; Node parent; } adds parent pointer which is optional. class Node { int data; Node left; Node right; int height; } adds height used in AVL trees, not basic BST.

3. Final Answer:

   class Node { int data; Node left; Node right; } -> Option A

4. Quick Check:

   Minimal node = data + left + right [OK]

Hint: Basic BST node has data and two child pointers only [OK]

Common Mistakes:

• Adding unnecessary fields like parent or height
• Confusing method declarations with node fields
• Using incorrect syntax for multiple variables

3. What will be the output of the following Java code snippet that inserts values into a BST and then performs an inorder traversal?

class Node {
  int data;
  Node left, right;
  Node(int d) { data = d; left = right = null; }
}

class BST {
  Node root;
  void insert(int val) { root = insertRec(root, val); }
  Node insertRec(Node root, int val) {
    if (root == null) return new Node(val);
    if (val < root.data) root.left = insertRec(root.left, val);
    else root.right = insertRec(root.right, val);
    return root;
  }
  void inorder(Node root) {
    if (root != null) {
      inorder(root.left);
      System.out.print(root.data + " ");
      inorder(root.right);
    }
  }
}

public class Main {
  public static void main(String[] args) {
    BST tree = new BST();
    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(7);
    tree.inorder(tree.root);
  }
}

medium

A. 10 5 7 15

B. 5 7 10 15

C. 7 5 10 15

D. 15 10 7 5

Solution

1. Step 1: Trace insertion order and BST structure

   Insert 10 as root. Insert 5 to left of 10. Insert 15 to right of 10. Insert 7 to right of 5.

2. Step 2: Perform inorder traversal

   Inorder visits left subtree, root, then right subtree. So nodes visited in order: 5, 7, 10, 15.

3. Final Answer:

   5 7 10 15 -> Option B

4. Quick Check:

   Inorder traversal = sorted values [OK]

Hint: Inorder traversal of BST prints sorted values [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Misplacing 7 in the tree structure
• Ignoring recursion order in traversal

4. The following code attempts to insert a value into a BST but causes a runtime error. What is the error?

class Node {
  int data;
  Node left, right;
  Node(int d) { data = d; }
}

class BST {
  Node root;
  void insert(int val) { root = insertRec(root, val); }
  Node insertRec(Node root, int val) {
    if (root == null) return new Node(val);
    if (val < root.data) root.left = insertRec(root.left, val);
    else root.right = insertRec(root.right, val);
    return root;
  }
}

medium

A. Compilation error due to missing return statement

B. StackOverflowError due to infinite recursion

C. No error, code runs fine

D. NullPointerException because left and right are not initialized in Node constructor

Solution

1. Step 1: Check Node constructor initialization

   In Java, Node left and right are automatically initialized to null by default. The constructor only sets data, which is sufficient.

2. Step 2: Analyze insertRec logic

   The base case handles null roots. Recursive calls like root.left = insertRec(root.left, val) are safe since insertRec(null) returns new Node without dereferencing null. All paths return a value. No runtime errors occur.

3. Final Answer:

   No error, code runs fine -> Option C

4. Quick Check:

   Default null + null base case = safe execution [OK]

Hint: Java defaults references to null; recursion base case prevents issues [OK]

Common Mistakes:

• Thinking uninitialized fields cause immediate NPE (defaults handle it)
• Suspecting infinite recursion (base case exists)
• Overlooking that all code paths return

5. You have a plain Binary Tree and want to convert it into a BST without changing its structure (only node values). Which approach is correct?

hard

A. Perform inorder traversal to collect values, sort them, then assign back during inorder traversal

B. Insert all nodes into a new BST and discard the old tree

C. Swap left and right children of all nodes to sort the tree

D. Replace each node value with the sum of its children

Solution

1. Step 1: Understand the problem constraints

   The tree structure must remain the same, so only node values can change. This means rearranging values to satisfy BST property without changing links.

2. Step 2: Use inorder traversal to collect and assign values

   Inorder traversal of BST gives sorted values. Collect all node values from the plain tree, sort them, then assign them back to nodes during inorder traversal to maintain structure but satisfy BST order.

3. Final Answer:

   Perform inorder traversal to collect values, sort them, then assign back during inorder traversal -> Option A

4. Quick Check:

   Sort values and reassign inorder = convert to BST [OK]

Hint: Sort values and reassign inorder to fix tree values [OK]

Common Mistakes:

• Changing tree structure instead of values
• Swapping children does not sort values
• Replacing values with sums breaks BST property