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.