Why BST Over Plain Binary Tree in DSA Javascript - Why It Was Designed This Way

Overview - Why BST Over Plain Binary Tree

What is it?

A plain binary tree is a simple tree structure where each node has up to two children without any specific order. A Binary Search Tree (BST) is a special kind of binary tree where the left child contains smaller values and the right child contains larger values than the parent node. This order helps in quickly finding, adding, or removing values. Understanding why BSTs are preferred over plain binary trees helps us see how data can be organized for faster searching.

Why it matters

Without the order of a BST, searching for a value in a plain binary tree can take a long time because you might have to check many nodes randomly. BSTs solve this by keeping data sorted, which makes searching much faster, like looking up a word in a dictionary instead of flipping pages randomly. This speed difference is crucial in many applications like databases, file systems, and games where quick data access matters.

Where it fits

Before learning this, you should understand what a binary tree is and basic tree terminology like nodes and children. After this, you can learn about balanced BSTs like AVL or Red-Black trees, which improve BST performance further, and then explore other data structures like heaps or hash tables.

Mental Model

Core Idea

A BST organizes data so that every left child is smaller and every right child is larger, enabling fast search and update operations compared to a plain binary tree.

Think of it like...

Imagine a phone book where names are sorted alphabetically. You can quickly find a name by deciding to look in the first half or second half, instead of checking every page randomly like in an unsorted notebook.

Plain Binary Tree vs BST

Plain Binary Tree:           BST:
      7                          7
     / \                        / \
    3   9                      3   9
   /     \                    /     \
  8       1                  1       10

In the plain tree, 8 is left of 3 and 1 is right of 9, no order.
In the BST, left children < parent < right children.

Build-Up - 7 Steps

1

Foundation

Understanding Plain Binary Trees

Concept: Learn what a plain binary tree is and how nodes connect without order.

A plain binary tree is a structure where each node can have up to two children. There is no rule about the values in the nodes. For example, the root node might have a value 7, its left child 3, and right child 9, but the children of 3 or 9 can be any values without restrictions.

Result

You can build any shape of tree, but searching for a value means checking many nodes randomly.

Knowing that plain binary trees have no order helps understand why searching can be slow and inefficient.

2

Foundation

Basic Search in Plain Binary Trees

Concept: Searching in a plain binary tree requires checking nodes without shortcuts.

To find a value, you start at the root and check if it matches. If not, you check the left child, then the right child, and so on, often using a method like depth-first or breadth-first search. This can mean visiting many nodes before finding the value or concluding it is not present.

Result

Searching can take time proportional to the number of nodes, because no order guides the search.

Understanding this slow search process shows why we need a better way to organize data.

3

Intermediate

Introducing Binary Search Tree Order

Concept: BSTs keep nodes ordered so left children are smaller and right children are larger than their parent.

In a BST, every node follows the rule: all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This order is maintained when inserting or deleting nodes. For example, if the root is 7, left children must be less than 7, right children greater than 7.

Result

This order allows skipping large parts of the tree when searching for a value.

Knowing this order is the key to faster search, insertion, and deletion compared to plain binary trees.

4

Intermediate

Searching in a BST vs Plain Tree

🤔Before reading on: Do you think searching in a BST always checks fewer nodes than in a plain binary tree? Commit to your answer.

Concept: BST search uses the order to decide which subtree to explore, reducing the number of nodes checked.

To search for a value in a BST, start at the root. If the value equals the root, you are done. If smaller, go to the left child; if larger, go to the right child. Repeat until you find the value or reach a leaf. This way, you ignore half the tree at each step, unlike plain trees where you might check every node.

Result

Search time in a BST is proportional to the height of the tree, often much less than total nodes.

Understanding this selective search explains why BSTs are much faster for lookups than plain binary trees.

5

Intermediate

Insertion and Deletion in BSTs

🤔Before reading on: Do you think insertion in a BST is simpler or more complex than in a plain binary tree? Commit to your answer.

Concept: Insertion and deletion in BSTs maintain the order property, which requires careful placement or rearrangement.

To insert, compare the new value with the root and move left or right accordingly until finding an empty spot. To delete, if the node has no or one child, replace it with the child or null. If two children, replace it with the smallest value in the right subtree (successor) to keep order. This keeps the BST property intact.

Result

BSTs stay ordered after insertions and deletions, preserving fast search ability.

Knowing how BSTs maintain order during updates is crucial for their reliability and performance.

6

Advanced

Performance Limits of BSTs

🤔Before reading on: Can a BST become as slow as a plain binary tree? Commit to your answer.

Concept: BSTs can degrade to a linked list if nodes are inserted in sorted order, losing their speed advantage.

If you insert values in ascending or descending order, the BST becomes skewed, with each node having only one child. This makes search, insertion, and deletion operations take time proportional to the number of nodes, like a plain binary tree or linked list. Balanced BSTs solve this problem by keeping the tree height small.

Result

Unbalanced BSTs can perform poorly, similar to plain binary trees.

Understanding this limitation motivates learning balanced BSTs and shows why plain BSTs are not always enough.

7

Expert

Why BSTs Are Preferred Over Plain Trees

🤔Before reading on: Do you think the main advantage of BSTs is only faster search, or are there other benefits? Commit to your answer.

Concept: BSTs provide ordered data storage enabling efficient search, insertion, deletion, and in-order traversal, unlike plain binary trees.

BSTs allow quick search by skipping half the tree at each step, fast insertion and deletion while maintaining order, and easy retrieval of sorted data through in-order traversal. Plain binary trees lack these benefits because they have no order, making operations slower and less predictable. This makes BSTs a foundational data structure in many algorithms and systems.

Result

BSTs combine order and flexibility, making them more powerful and practical than plain binary trees.

Recognizing the multiple advantages of BSTs beyond just search speed deepens appreciation for their design and use.

Under the Hood

A BST stores nodes in memory with pointers to left and right children. The order property means that for any node, all nodes in the left subtree have smaller values and all in the right subtree have larger values. This allows the search algorithm to decide direction at each node, reducing the search space by half each time. Insertions and deletions adjust pointers carefully to maintain this order. Internally, the tree's shape affects performance; balanced shapes keep operations fast, while skewed shapes slow them down.

Why designed this way?

BSTs were designed to improve search efficiency over unordered trees by imposing a simple ordering rule. This rule is easy to maintain during insertions and deletions and enables binary search-like speed on tree structures. Alternatives like hash tables offer faster average search but lack order, while balanced BSTs improve worst-case performance. The BST strikes a balance between simplicity, order, and efficiency.

BST Node Structure and Search Flow

  [Node: Value]
     /       \
[Left Child] [Right Child]

Search for X:
  Start at root
  ├─ If X == Node.Value: found
  ├─ If X < Node.Value: go left subtree
  └─ If X > Node.Value: go right subtree

Repeat until found or leaf reached.

Myth Busters - 4 Common Misconceptions

Quick: Does a BST always guarantee faster search than a plain binary tree? Commit to yes or no.

Common Belief: A BST always searches faster than a plain binary tree because of its order.

Reality: If a BST becomes unbalanced (like a linked list), its search time can be as slow as a plain binary tree.

Why it matters: Assuming BSTs are always fast can lead to poor performance if the tree is not balanced, causing unexpected slowdowns.

Quick: Is the order property of BSTs only useful for searching? Commit to yes or no.

Common Belief: The BST order only helps with searching, not with other operations.

Reality: The order also helps with efficient insertion, deletion, and retrieving sorted data via in-order traversal.

Why it matters: Ignoring these benefits can limit understanding of BSTs and their full usefulness in applications.

Quick: Can a plain binary tree be used to quickly find the smallest or largest value? Commit to yes or no.

Common Belief: You can quickly find the smallest or largest value in any binary tree by checking the root or its immediate children.

Reality: In a plain binary tree, smallest or largest values can be anywhere, requiring a full traversal to find them.

Why it matters: Misunderstanding this leads to inefficient code that assumes quick access to extremes in unordered trees.

Quick: Is the main reason to use BSTs to save memory compared to plain binary trees? Commit to yes or no.

Common Belief: BSTs save memory compared to plain binary trees because of their structure.

Reality: BSTs use the same amount of memory as plain binary trees; their advantage is in operation speed, not memory savings.

Why it matters: Confusing memory use with speed can cause wrong expectations and design choices.

Expert Zone

1

BST performance depends heavily on tree shape; subtle insertion orders can cause skewing unnoticed until performance degrades.

2

In-order traversal of BSTs yields sorted data without extra sorting steps, a powerful property used in many algorithms.

3

BSTs can be augmented with extra data (like counts or sums) at nodes to support advanced queries efficiently.

When NOT to use

Avoid plain BSTs when data is inserted in sorted or nearly sorted order, as they degrade to linked lists. Use balanced BSTs like AVL or Red-Black trees instead. For unordered data with frequent random access, hash tables may be better. For priority-based access, heaps are preferable.

Production Patterns

BSTs are used in databases for indexing, in-memory sorted sets, and language libraries for ordered collections. Balanced BST variants are common in production to guarantee performance. BSTs also underpin interval trees and segment trees for range queries.

Connections

Balanced Binary Search Trees

Builds-on

Understanding BSTs is essential before learning balanced BSTs, which fix BST performance issues by keeping the tree height small.

Hash Tables

Alternative data structure

Comparing BSTs with hash tables highlights trade-offs between ordered data access and average-case constant-time lookup.

Library Book Indexing

Real-world ordering system

Like BSTs, library indexes organize books by order to quickly find titles, showing how ordering speeds up search in many fields.

Common Pitfalls

#1 Assuming BSTs always provide fast search regardless of insertion order.

Wrong approach:

Insert values 1, 2, 3, 4, 5 into BST without balancing, expecting O(log n) search time.

Correct approach:

Use a balanced BST or insert values in a way that keeps the tree balanced to maintain O(log n) search time.

Root cause:

Not understanding that unbalanced BSTs degrade to linked lists, losing their speed advantage.

#2 Trying to find the smallest value in a plain binary tree by checking only the root or immediate children.

Wrong approach:

Return root.value or root.left.value as smallest in a plain binary tree.

Correct approach:

Traverse the entire tree to find the smallest value when no order is guaranteed.

Root cause:

Misunderstanding that plain binary trees have no ordering, so smallest values can be anywhere.

#3 Deleting a node in BST without maintaining the order property.

Wrong approach:

Remove a node and replace it with any child without adjusting the tree properly.

Correct approach:

Replace the node with its in-order successor or predecessor to keep BST order intact.

Root cause:

Not knowing the deletion rules that preserve BST structure.

Key Takeaways

Plain binary trees have no order, making search and updates slow and unpredictable.

BSTs impose a simple order rule that enables fast search, insertion, and deletion by guiding traversal direction.

BST performance depends on tree shape; unbalanced BSTs can be as slow as plain trees.

BSTs allow easy retrieval of sorted data through in-order traversal, a key advantage over plain trees.

Understanding BSTs is foundational before learning balanced trees or other advanced data structures.