Why BST Over Plain Binary Tree in DSA Java - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why choose a BST over a plain binary tree?

Which of the following best explains why a Binary Search Tree (BST) is preferred over a plain binary tree for searching operations?

A BST keeps elements sorted, allowing faster search by skipping half of the tree at each step.

B BST uses less memory than a plain binary tree because it stores fewer nodes.

C BST allows duplicate values which plain binary trees do not support.

D BST nodes have pointers to parents, which plain binary trees do not have.

💡 Hint

Think about how searching works in a sorted structure compared to an unsorted one.

A BST keeps its elements in sorted order, so when searching, it can decide to go left or right subtree based on comparison, effectively skipping half the nodes each time. This makes search operations faster than in a plain binary tree where nodes are unordered.

❓ Predict Output

intermediate

Output of searching in BST vs plain binary tree

Consider the following Java code snippets for searching a value in two trees: a BST and a plain binary tree. What will be the output when searching for value 7? (Assume the same tree structure is used for both.)

DSA Java

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

// BST search method
boolean searchBST(Node root, int key) {
  if (root == null) return false;
  if (root.val == key) return true;
  if (key < root.val) return searchBST(root.left, key);
  else return searchBST(root.right, key);
}

// Plain binary tree search method
boolean searchPlain(Node root, int key) {
  if (root == null) return false;
  if (root.val == key) return true;
  return searchPlain(root.left, key) || searchPlain(root.right, key);
}

// Tree setup: root=5, left=3, right=8, 8.left=7 (contains 7, valid BST)

A searchBST returns true; searchPlain returns true

B searchBST returns false; searchPlain returns true

C searchBST returns true; searchPlain returns false

D searchBST returns false; searchPlain returns false

💡 Hint

Both methods search for the value 7, but one uses BST logic and the other searches all nodes. The tree contains 7.

Both search methods will find the value 7 since it exists in the tree. The BST search uses the sorted property to find it efficiently (O(log n)), while the plain binary tree search checks all nodes recursively (O(n)).

🔧 Debug

advanced

Why does this BST search code fail on some inputs?

Given the following Java method to search a BST, why does it fail to find some values?

DSA Java

boolean searchBST(Node root, int key) {
  if (root == null) return false;
  if (key <= root.val) return searchBST(root.left, key);
  if (root.val == key) return true;
  return searchBST(root.right, key);
}

A The method does not check for null nodes before accessing root.val, causing NullPointerException.

B The method should search both left and right subtrees to find the key in a BST.

C The method should return false immediately after the first recursive call.

D Using <= instead of < causes the search to go left even when key equals root.val, missing the correct node.

💡 Hint

Think about what happens when key equals root.val and the condition uses <=.

Since the equality check comes after the <= condition, when key == root.val, the if (key <= root.val) evaluates to true and recurses left without ever reaching the equality check, missing the node at the current position.

📝 Syntax

advanced

Which code snippet correctly inserts a value into a BST?

Which of the following Java methods correctly inserts a new integer value into a BST?

A

Node insert(Node root, int val) {
  if (root == null) return new Node(val);
  if (val > root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

B

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

C

Node insert(Node root, int val) {
  if (root == null) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else if (val > root.val) root.right = insert(root.right, val);
  return root;
}

D

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

💡 Hint

Remember to assign the recursive call result back to the child node pointer.

Option C correctly assigns the recursive insert result to root.left or root.right and returns root. It also handles no duplicates (if val == root.val, does nothing). Option C allows duplicates on left (common alternative). Option C reverses left/right logic. Option C does not assign recursive calls, so tree is not updated.

🚀 Application

expert

How does BST improve average search time compared to plain binary tree?

Assuming a tree with n nodes, what is the average time complexity of searching for a value in a balanced BST compared to a plain binary tree?

A BST: O(1) average; Plain binary tree: O(n) average

B BST: O(log n) average; Plain binary tree: O(n) average

C BST: O(n log n) average; Plain binary tree: O(n) average

D BST: O(n) average; Plain binary tree: O(log n) average

💡 Hint

Think about how balanced trees reduce the height compared to unstructured trees.

A balanced BST has height about log n, so searching takes O(log n) time on average. A plain binary tree with no order may require checking all nodes in the worst/average case, so O(n) time.

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