Properties of a Binary Search Tree

1. From Binary Tree to Binary Search Tree

A Binary Search Tree is, first and foremost, a binary tree. This means every node has at most two children. However, a BST adds a crucial constraint that organizes the data in a predictable way.

To get a clear initial picture of this distinction and the core idea behind a BST, let's start with a short video.

2. The Core Properties of a BST

As you saw in the video, the "search" in Binary Search Tree comes from a specific set of ordering rules. These properties must hold true for every single node in the tree.

Formally, a Binary Search Tree has the following properties:

1. The Left Subtree Property: For any given node, all values in its left subtree are strictly less than the node's own value.
2. The Right Subtree Property: For any given node, all values in its right subtree are strictly greater than the node's own value.
3. The BST Property for Subtrees: Both the left and right subtrees must also be binary search trees. This recursive definition ensures the ordering rules apply throughout the entire tree.

Additionally, it's a common convention that BSTs do not contain duplicate values. This simplifies many operations, and we will follow this convention.

Let's look at some visual examples to solidify this.

    10
   /  \
  5    15
 / \    \
3   7    18
     \
      11 

3. Why These Properties Matter: The "Search" Advantage

The rigid structure of a BST is what makes it so powerful. When you're searching for a value, these ordering properties allow you to eliminate half of the remaining tree at every step, much like how binary search works on a sorted array.

Let's trace the search for the value 23 in the tree from the video:

1. Start at the root (15). 23 > 15, so we know 23 must be in the right subtree. We discard the entire left half.
2. Move to the new node (27). 23 < 27, so 23 must be in the left subtree of 27.
3. Move to the new node (20). 23 > 20, so 23 must be in the right subtree of 20.
4. Move to the new node (23). We found it!

This efficient process is the primary reason for using a BST. The following video segment explains this logic and its performance implications.

As the video explains, this search operation has a time complexity of $O(\log n)$. This is a massive improvement over the $O(n)$ search in an unordered list or a general binary tree. It's important to note that this performance is achieved when the tree is balanced. If the tree is heavily unbalanced (e.g., looking like a linked list), the performance can degrade to $O(n)$. We will explore balanced BSTs later in the course.

4. A Key Consequence: In-Order Traversal

Recall from the previous module that an in-order traversal of a binary tree follows the pattern: Left -> Root -> Right.

What do you think happens when you perform an in-order traversal on a Binary Search Tree?

Because of the BST's ordering property (all left values < root value < all right values), an in-order traversal will visit the nodes in ascending sorted order. This is an incredibly useful and elegant consequence of the BST structure. It also provides a simple way to verify if a given binary tree is a valid BST.

The following article explains this concept and provides a clear example.

Conclusion

In this lesson, we've defined the fundamental properties of a Binary Search Tree, which sets the stage for the rest of this module.

Key Takeaways:

• A BST is a binary tree with a specific ordering rule that must apply to every node.
• The Ordering Property: For any node N, all values in its left subtree are less than N's value, and all values in its right subtree are greater than N's value.
• BSTs generally do not contain duplicate values.
• This structure enables highly efficient search operations, typically $O(\log n)$ for balanced trees, because half of the search space can be eliminated at each step.
• A key consequence of the BST properties is that an in-order traversal visits the nodes in ascending sorted order.

Up Next:
Now that you understand what a BST is and why it's useful, our next lesson will focus on the "how". We'll begin implementing the core operations for a BST, starting with searching for a value and inserting a new node while maintaining the BST properties.