BST Properties and Rules

Binary Search Trees (BSTs): Properties and Rules

The Binary Search Tree (BST) is a special type of binary tree that maintains a specific ordering property, making it highly efficient for searching, insertion, and deletion operations. This ordering allows us to quickly narrow down the search space, similar to how binary search works on a sorted array.

---

1. Defining Properties of a BST

For a binary tree to be considered a Binary Search Tree, it must adhere to the following rules for every node within the tree:

• Left Subtree Property: All values in the left subtree of a node must be less than the value of the node itself.
• Right Subtree Property: All values in the right subtree of a node must be greater than the value of the node itself.
• Recursive Property: Both the left and right subtrees must also be Binary Search Trees.

These properties ensure that an inorder traversal of a BST will yield the node values in sorted (ascending) order.

---

2. Handling Duplicate Values

When designing a BST, a crucial decision is how to handle duplicate values. There are a few common strategies:

• Disallow Duplicates: The simplest approach is to simply not allow duplicate values to be inserted into the BST. If an attempt is made to insert a duplicate, the operation might fail or do nothing.
• Allow Duplicates on One Side: Duplicates can be allowed by consistently placing them on either the left or right side of the existing node. For example:
  • If newValue <= currentNode.value, go left.
  • If newValue > currentNode.value, go right.
  • Consistency is key: Once a rule is chosen, it must be applied uniformly to maintain the BST property.
• Store Counts in Nodes: Instead of adding duplicate nodes, each node can store a count of how many times its value appears in the tree.

The chosen policy must be consistent to ensure correct search and traversal behavior.

---

3. Impact of Tree Shape on Performance

The efficiency of BST operations (search, insertion, deletion) is directly related to the height of the tree.

• Average Case Performance: If elements are inserted in a random order, the BST tends to be relatively balanced, resulting in a height of approximately O(log N), where N is the number of nodes. In this average case, all primary operations (search, insert, delete) have a time complexity of O(log N).
• Worst Case Performance: If elements are inserted in an already sorted (ascending or descending) order, the BST can degenerate into a skewed tree, resembling a linked list. In this worst case, the height becomes O(N), and operations can take O(N) time, losing the benefits of a tree structure.

To mitigate the worst-case scenario, Self-Balancing Binary Search Trees (like AVL trees and Red-Black trees) automatically adjust their structure during insertions and deletions to ensure the height remains logarithmic, thus guaranteeing O(log N) performance for all operations.

---

Key Takeaway: The strict ordering rules of BSTs enable efficient data retrieval and manipulation. However, their performance heavily relies on maintaining a balanced structure. Understanding these properties is fundamental to both implementing BSTs correctly and appreciating the need for self-balancing variants in practical applications.

---

Interactive: Build a BST by Inserting Values

Use the visualizer below to insert values one by one and see how the tree grows. Try different sequences (e.g., sorted input) to observe how shape affects height.