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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why is a BST more efficient than a plain binary tree for search?

Consider searching for a value in a plain binary tree versus a binary search tree (BST). Why does a BST generally allow faster search?

A Because BST nodes are arranged so that left children are smaller and right children are larger, allowing skipping half the tree at each step.

B Because BSTs store values in a linked list inside each node, making search faster.

C Because plain binary trees always have more nodes than BSTs, so searching is slower.

D Because BSTs use hashing internally to find values instantly.

💡 Hint

Think about how the order of nodes helps decide which branch to follow during search.

A BST keeps nodes in order: left child smaller, right child larger. This lets you decide to go left or right at each step, skipping half the nodes, making search faster than checking every node in a plain binary tree.

❓ Predict Output

intermediate

Output of searching in a plain binary tree vs BST

Given the following Go code snippets for searching a value in two trees, what is the output?

DSA Go

package main
import "fmt"

type Node struct {
    Val int
    Left, Right *Node
}

// Plain binary tree search: checks all nodes
func searchPlain(root *Node, target int) bool {
    if root == nil {
        return false
    }
    if root.Val == target {
        return true
    }
    return searchPlain(root.Left, target) || searchPlain(root.Right, target)
}

// BST search: uses ordering to decide path
func searchBST(root *Node, target int) bool {
    if root == nil {
        return false
    }
    if root.Val == target {
        return true
    } else if target < root.Val {
        return searchBST(root.Left, target)
    } else {
        return searchBST(root.Right, target)
    }
}

func main() {
    // Plain binary tree
    rootPlain := &Node{Val: 10}
    rootPlain.Left = &Node{Val: 5}
    rootPlain.Right = &Node{Val: 15}
    rootPlain.Left.Left = &Node{Val: 3}
    rootPlain.Right.Right = &Node{Val: 20}

    // BST with same values
    rootBST := &Node{Val: 10}
    rootBST.Left = &Node{Val: 5}
    rootBST.Right = &Node{Val: 15}
    rootBST.Left.Left = &Node{Val: 3}
    rootBST.Right.Right = &Node{Val: 20}

    fmt.Println(searchPlain(rootPlain, 20))
    fmt.Println(searchBST(rootBST, 20))
}

A

false
false

B

true
true

C

true
false

D

false
true

💡 Hint

Both trees contain the value 20. Check if both search functions find it.

Both searchPlain and searchBST find the value 20 in their respective trees, so both print true.

❓ Predict Output

advanced

Result of inserting values in a plain binary tree vs BST

What is the printed structure after inserting values 10, 5, 15, 3, 20 into a plain binary tree and a BST?

DSA Go

package main
import "fmt"

type Node struct {
    Val int
    Left, Right *Node
}

// Insert in plain binary tree: always to left if possible
func insertPlain(root *Node, val int) *Node {
    if root == nil {
        return &Node{Val: val}
    }
    if root.Left == nil {
        root.Left = insertPlain(root.Left, val)
    } else {
        root.Right = insertPlain(root.Right, val)
    }
    return root
}

// Insert in BST
func insertBST(root *Node, val int) *Node {
    if root == nil {
        return &Node{Val: val}
    }
    if val < root.Val {
        root.Left = insertBST(root.Left, val)
    } else {
        root.Right = insertBST(root.Right, val)
    }
    return root
}

func printInOrder(root *Node) {
    if root == nil {
        return
    }
    printInOrder(root.Left)
    fmt.Print(root.Val, " ")
    printInOrder(root.Right)
}

func main() {
    var rootPlain *Node
    vals := []int{10, 5, 15, 3, 20}
    for _, v := range vals {
        rootPlain = insertPlain(rootPlain, v)
    }

    var rootBST *Node
    for _, v := range vals {
        rootBST = insertBST(rootBST, v)
    }

    printInOrder(rootPlain)
    fmt.Println()
    printInOrder(rootBST)
}

A

3 5 10 15 20 
3 5 10 15 20 

B

20 15 10 5 3 
3 5 10 15 20 

C

3 5 10 15 20 
20 15 10 5 3 

D

5 10 3 15 20 
3 5 10 15 20 

💡 Hint

In-order traversal of BST prints sorted values. Plain binary tree insertion is not ordered but in-order traversal still visits left-root-right.

In-order traversal prints nodes in ascending order for BST ('3 5 10 15 20'). For plain binary tree, the left-preferred insertion results in '5 10 3 15 20', demonstrating no ordering guarantee.

🧠 Conceptual

advanced

Why can a plain binary tree cause slower search than a BST?

Which reason best explains why searching in a plain binary tree can be slower than in a BST?

A Because plain binary trees do not maintain any order, so search must check every node potentially.

B Because plain binary trees use more memory, slowing down search.

C Because plain binary trees always have more levels than BSTs.

D Because plain binary trees store duplicate values which confuse search.

💡 Hint

Think about how order helps reduce search steps.

Plain binary trees have no ordering rules, so to find a value you may need to check every node. BSTs use ordering to skip large parts of the tree during search.

🚀 Application

expert

Choosing data structure for fast search in large data

You have a large set of numbers and need to perform many searches quickly. Which data structure is best and why?

A Use an unsorted array because arrays have fast access by index.

B Use a plain binary tree because it is simpler to implement and uses less memory.

C Use a balanced BST because it keeps data ordered and allows fast O(log n) search.

D Use a linked list because it allows easy insertion and deletion.

💡 Hint

Consider search time complexity and data ordering.

A balanced BST keeps data sorted and balanced, allowing searches in O(log n) time, which is much faster than linear search in arrays or linked lists.

Practice

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

easy

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

B. Because BST keeps elements in a sorted order allowing faster search

C. Because BST nodes can have more than two children

D. Because BST does not require pointers to child nodes

Solution

1. Step 1: Understand the structure difference

   A plain Binary Tree has no order among nodes, while BST keeps nodes sorted so left child is smaller and right child is larger.

2. Step 2: Analyze search efficiency

   Because BST is sorted, searching can skip half the tree at each step, making search faster than in a plain Binary Tree.

3. Final Answer:

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

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
• Believing BST does not use pointers

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

easy

A. type Node struct { value int; left *Node; right *Node }

B. type Node struct { value int; left Node; right Node }

C. type Node struct { value int; left *int; right *int }

D. type Node struct { value int; left interface{}; right interface{} }

Solution

1. Step 1: Understand pointer usage in Go structs

   BST nodes must point to child nodes, so left and right should be pointers to Node type.

2. Step 2: Check each option

   type Node struct { value int; left *Node; right *Node } uses *Node pointers correctly. type Node struct { value int; left Node; right Node } uses Node directly, causing infinite size. type Node struct { value int; left *int; right *int } uses *int which is wrong type. type Node struct { value int; left interface{}; right interface{} } uses interface{} which is too generic and not typical for BST.

3. Final Answer:

   type Node struct { value int; left *Node; right *Node } -> Option A

4. Quick Check:

   Pointers to Node = correct struct [OK]

Hint: BST nodes use pointers to child nodes in Go [OK]

Common Mistakes:

• Using non-pointer fields causing infinite struct size
• Using wrong pointer types like *int
• Using interface{} instead of concrete types

3. What will be the output of the following Go code that inserts values into a BST and prints inorder traversal?

package main
import "fmt"
type Node struct {
  value int
  left, right *Node
}
func insert(root *Node, val int) *Node {
  if root == nil {
    return &Node{value: val}
  }
  if val < root.value {
    root.left = insert(root.left, val)
  } else {
    root.right = insert(root.right, val)
  }
  return root
}
func inorder(root *Node) {
  if root != nil {
    inorder(root.left)
    fmt.Print(root.value, " ")
    inorder(root.right)
  }
}
func main() {
  var root *Node
  values := []int{7, 3, 9, 1, 5}
  for _, v := range values {
    root = insert(root, v)
  }
  inorder(root)
}

medium

A. 1 3 5 7 9

B. 7 3 9 1 5

C. 9 7 5 3 1

D. 3 1 5 7 9

Solution

1. Step 1: Insert values into BST

   Insert 7 as root, then 3 to left, 9 to right, 1 to left of 3, 5 to right of 3.

2. Step 2: Perform inorder traversal

   Inorder visits left subtree, root, then right subtree. So nodes print in sorted order: 1 3 5 7 9.

3. Final Answer:

   1 3 5 7 9 -> Option A

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 nodes during insertion
• Printing values without spaces

4. The following Go code tries to insert values into a BST but causes a runtime error. What is the error?

package main
import "fmt"
type Node struct {
  value int
  left, right *Node
}
func insert(root *Node, val int) {
  if root == nil {
    root = &Node{value: val}
    return
  }
  if val < root.value {
    insert(root.left, val)
  } else {
    insert(root.right, val)
  }
}
func main() {
  var root *Node
  insert(root, 10)
  insert(root, 5)
  insert(root, 15)
  fmt.Println(root)
}

medium

A. Panic due to nil pointer dereference

B. Stack overflow due to infinite recursion

C. Compilation error due to missing return type

D. root remains nil because insert does not update root pointer

Solution

1. Step 1: Analyze insert function parameter

   insert takes root as value, not pointer to pointer, so changes to root inside insert do not affect caller.

2. Step 2: Understand effect on root variable

   root in main remains nil because insert does not update it outside its scope, so tree is never built.

3. Final Answer:

   root remains nil because insert does not update root pointer -> Option D

4. Quick Check:

   Pointer not updated = root nil [OK]

Hint: Pass pointer to pointer to update root in insert [OK]

Common Mistakes:

• Assuming root updates inside insert affect main
• Ignoring pointer semantics in Go
• Confusing runtime error with logical error

5. You want to store a large set of numbers and perform frequent searches. Why would using a BST be better than a plain Binary Tree, and what is the worst-case time complexity of search in a BST?

hard

A. Plain Binary Tree has better search time than BST

B. BST always guarantees O(1) search time due to sorting

C. BST allows faster average search (O(log n)) but worst-case can be O(n) if unbalanced

D. BST uses less memory and has O(n^2) search time in worst case

Solution

1. Step 1: Compare search efficiency

   BST keeps elements sorted, so average search is O(log n), faster than plain Binary Tree which has no order.

2. Step 2: Consider worst-case scenario

   If BST becomes unbalanced (like a linked list), search degrades to O(n) time.

3. Final Answer:

   BST allows faster average search (O(log n)) but worst-case can be O(n) if unbalanced -> Option C

4. Quick Check:

   Average O(log n), worst O(n) in BST [OK]

Hint: BST average search O(log n), worst O(n) if unbalanced [OK]

Common Mistakes:

• Thinking BST always has O(1) search
• Confusing plain Binary Tree search time
• Ignoring unbalanced BST worst case