Why BST Over Plain Binary Tree in DSA Go - Why This Pattern

Mental Model

A Binary Search Tree (BST) keeps data sorted so we can find things fast, unlike a plain binary tree which has no order.

Analogy: Imagine a phone book: names are sorted alphabetically so you can quickly find a number. A plain binary tree is like a random pile of papers with names scattered everywhere.

Plain Binary Tree:
    5
   / \
  3   8
 /     \
7       9
/ 
2 

BST:
    5
   / \
  3   8
 /     \
2       9

Dry Run Walkthrough

Input: Plain binary tree with nodes 5(root),3(left),8(right),7(3.left),2(7.left),9(8.right); BST with nodes 5,3(left),8(right),2(3.left),9(8.right)

Goal: Show how searching for 2 differs in speed and steps between plain binary tree and BST

Step 1: Start search for 2 at root 5 (!=2) in both trees

Plain: [5] ; BST: [5]

Why: Always check the root node first in tree search

Step 2: Plain recurses to left child 3 (!=2); BST goes left (2 < 5) to 3 (!=2)

Plain: 5 -> [3] ; BST: 5 -> [3]

Why: Plain tree checks left subtree first (DFS order); BST uses < to go left

Step 3: Plain recurses to left of 3: 7 (!=2); BST goes left (2 < 3) to 2 (==2, found!)

Plain: 5 -> 3 -> [7] ; BST: 5 -> 3 -> [2] FOUND

Why: Plain has no order, blindly checks 3.left=7 (>2, unnecessary); BST order guides directly left to 2

Step 4: Plain recurses to left of 7: 2 (==2, found!)

Plain: 5 -> 3 -> 7 -> [2] FOUND ; BST: already found after 3 steps

Why: Plain finds 2 but after extra unnecessary visit to 7

Result:

Plain Tree: found 2 after 4 steps/nodes visited (5->3->7->2)
BST: found 2 after 3 steps/nodes visited (5->3->2)
BST skips irrelevant nodes using order property

Annotated Code

DSA Go

package main

import "fmt"

// Node represents a node in a binary tree
type Node struct {
	val   int
	left  *Node
	right *Node
}

// SearchPlain searches for a value in a plain binary tree (no order)
func SearchPlain(root *Node, target int) bool {
	if root == nil {
		return false
	}
	if root.val == target {
		return true
	}
	// Search left subtree
	if SearchPlain(root.left, target) {
		return true
	}
	// Search right subtree
	return SearchPlain(root.right, target)
}

// SearchBST searches for a value in a BST using order
func SearchBST(root *Node, target int) bool {
	if root == nil {
		return false
	}
	if root.val == target {
		return true
	}
	if target < root.val {
		return SearchBST(root.left, target) // go left if smaller
	} else {
		return SearchBST(root.right, target) // go right if bigger or equal
	}
}

func main() {
	// Plain binary tree
	plain := &Node{5, nil, nil}
	plain.left = &Node{3, nil, nil}
	plain.right = &Node{8, nil, nil}
	plain.left.left = &Node{7, nil, nil}
	plain.left.left.left = &Node{2, nil, nil}
	plain.right.right = &Node{9, nil, nil}

	// BST
	bst := &Node{5, nil, nil}
	bst.left = &Node{3, nil, nil}
	bst.right = &Node{8, nil, nil}
	bst.left.left = &Node{2, nil, nil}
	bst.right.right = &Node{9, nil, nil}

	fmt.Println("Search 2 in plain binary tree:", SearchPlain(plain, 2))
	fmt.Println("Search 2 in BST:", SearchBST(bst, 2))
}

if root == nil { return false }

stop search if reached empty node

if root.val == target { return true }

found target value

if SearchPlain(root.left, target) { return true } ; return SearchPlain(root.right, target)

search left then right subtrees in plain tree (no order, checks both if needed)

if target < root.val { return SearchBST(root.left, target) } else { return SearchBST(root.right, target) }

use BST order to decide which subtree to search (skips half)

Output

Search 2 in plain binary tree: true

Search 2 in BST: true

Complexity Analysis

Time: O(n) for plain binary tree because we may check every node without order

Space: O(h) where h is tree height due to recursion stack in both trees

vs Alternative: BST search is faster on average O(log n) because it skips half the tree each step, unlike plain tree which checks all nodes

Edge Cases

Empty tree

Search returns false immediately

DSA Go

if root == nil { return false }

Target not in tree

Search explores all nodes in plain tree, or follows BST path until leaf

DSA Go

if root == nil { return false }

Single node tree with target

Search finds target immediately

DSA Go

if root.val == target { return true }

When to Use This Pattern

When you need fast search in a tree and data is sorted, reach for BST because it uses order to skip half the nodes each step.

Common Mistakes

Mistake: Trying to search a BST like a plain tree by checking both children always
Fix: Use the BST property to decide only one subtree to search based on comparison

Summary

A BST keeps nodes in order to speed up search compared to a plain binary tree.

Use a BST when you want faster search, insert, or delete operations on sorted data.

The key insight is that BST order lets you ignore half the tree at each step, making search faster.