Why BST Over Plain Binary Tree in DSA Go - Performance Analysis

Time Complexity: Why BST Over Plain Binary Tree

O(n) for plain binary tree, O(log n) for balanced BST

Understanding Time Complexity

We want to understand why a Binary Search Tree (BST) is faster than a plain Binary Tree for searching data.

How does the structure affect the time it takes to find a value?

Scenario Under Consideration

Analyze the time complexity of searching a value in these trees.

// Search in plain binary tree (no order)
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)
}

// Search in BST (ordered)
func SearchBST(root *Node, val int) bool {
  if root == nil {
    return false
  }
  if val == root.Value {
    return true
  } else if val < root.Value {
    return SearchBST(root.Left, val)
  } else {
    return SearchBST(root.Right, val)
  }
}
    

This code shows searching for a value in a plain binary tree and in a BST.

Identify Repeating Operations

Look at what repeats during the search.

• Primary operation: Visiting nodes to check their values.
• How many times:
  • Plain tree: May visit almost all nodes (traverse entire tree).
  • BST: Visits nodes along one path from root to leaf.

How Execution Grows With Input

As the number of nodes (n) grows, how many nodes do we check?

Input Size (n)	Approx. Operations Plain Tree	Approx. Operations BST
10	Up to 10 nodes	Up to 4 nodes (height ~ log2 10)
100	Up to 100 nodes	Up to 7 nodes (height ~ log2 100)
1000	Up to 1000 nodes	Up to 10 nodes (height ~ log2 1000)

Pattern observation: Plain tree search grows linearly with n, but BST search grows slowly with tree height, which is about log n.

Final Time Complexity

Time Complexity: O(n) for plain binary tree search, O(log n) for balanced BST search

This means searching in a BST is much faster because it skips large parts of the tree by using order.

Common Mistake

[X] Wrong: "A BST always searches in O(log n) time no matter what."

[OK] Correct: If the BST is unbalanced (like a linked list), search can degrade to O(n), same as a plain tree.

Interview Connect

Understanding why BSTs are faster helps you explain data structure choices clearly and shows you know how structure affects speed.

Self-Check

"What if the BST is not balanced? How would that affect the search time complexity?"