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

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of numbers and you want to find, add, or check if a number exists quickly. You can store these numbers in a tree structure. But not all trees are equal. A plain binary tree just puts numbers anywhere, while a Binary Search Tree (BST) keeps them in order.This project will help you see why BST is better than a plain binary tree for searching numbers.

🎯 Goal: You will create two trees: a plain binary tree and a BST with the same numbers. Then, you will search for a number in both trees and see the difference in how they work.

📋 What You'll Learn

Create a plain binary tree with nodes containing integers

Create a Binary Search Tree (BST) with the same integers

Write a function to search for a number in the plain binary tree

Write a function to search for a number in the BST

Print the search results for both trees

💡 Why This Matters

🌍 Real World

BSTs are used in databases, file systems, and many software tools to quickly find, add, or remove data.

💼 Career

Understanding BSTs is essential for software developers and engineers to write efficient code for searching and sorting data.

1

Create a plain binary tree with nodes

Create a struct called Node with an integer value and two pointers left and right to Node. Then create a root node called plainRoot with value 10. Set its left child to a node with value 5 and right child to a node with value 15.

DSA Go

type Node struct {
    value int
    left  *Node
    right *Node
}

// Create plain binary tree root
// Your code here

Hint

Define the Node struct first. Then create plainRoot and assign its children.

2

Create a Binary Search Tree (BST) with the same numbers

Create a function called insertBST that takes a pointer to Node and an integer val. It inserts val into the BST following BST rules. Then create a root node called bstRoot with value 10 and insert 5 and 15 using insertBST.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func insertBST(root *Node, val int) *Node {
    // Your code here
    return root
}

func main() {
    plainRoot := &Node{value: 10}
    plainRoot.left = &Node{value: 5}
    plainRoot.right = &Node{value: 15}

    // Create BST root and insert values
    // Your code here
}

Hint

Use recursion to insert values in the BST. Remember to return the root after insertion.

3

Write search functions for plain binary tree and BST

Write a function called searchPlain that searches for an integer val in the plain binary tree by checking current node and then recursively searching left and right children. Write another function called searchBST that searches for val in the BST using BST rules (go left if val is less, right if val is more). Both functions return true if found, false otherwise.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func insertBST(root *Node, val int) *Node {
    if root == nil {
        return &Node{value: val}
    }
    if val < root.value {
        root.left = insertBST(root.left, val)
    } else {
        root.right = insertBST(root.right, val)
    }
    return root
}

func searchPlain(root *Node, val int) bool {
    // Your code here
    return false
}

func searchBST(root *Node, val int) bool {
    // Your code here
    return false
}

func main() {
    plainRoot := &Node{value: 10}
    plainRoot.left = &Node{value: 5}
    plainRoot.right = &Node{value: 15}

    bstRoot := &Node{value: 10}
    bstRoot = insertBST(bstRoot, 5)
    bstRoot = insertBST(bstRoot, 15)
}

Hint

For searchPlain, check current node then both children. For searchBST, use the value comparison to decide direction.

4

Print search results for both trees

In main, search for the value 15 in both plainRoot and bstRoot using searchPlain and searchBST. Print "Found in plain tree" if found in plain tree, else "Not found in plain tree". Similarly, print "Found in BST" or "Not found in BST" for the BST search.

DSA Go

package main

type Node struct {
    value int
    left  *Node
    right *Node
}

func insertBST(root *Node, val int) *Node {
    if root == nil {
        return &Node{value: val}
    }
    if val < root.value {
        root.left = insertBST(root.left, val)
    } else {
        root.right = insertBST(root.right, val)
    }
    return root
}

func searchPlain(root *Node, val int) bool {
    if root == nil {
        return false
    }
    if root.value == val {
        return true
    }
    return searchPlain(root.left, val) || searchPlain(root.right, val)
}

func searchBST(root *Node, val int) bool {
    if root == nil {
        return false
    }
    if root.value == val {
        return true
    }
    if val < root.value {
        return searchBST(root.left, val)
    }
    return searchBST(root.right, val)
}

func main() {
    plainRoot := &Node{value: 10}
    plainRoot.left = &Node{value: 5}
    plainRoot.right = &Node{value: 15}

    bstRoot := &Node{value: 10}
    bstRoot = insertBST(bstRoot, 5)
    bstRoot = insertBST(bstRoot, 15)

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

Hint

Use if statements to check search results and print the exact messages.