Properties of a BST

Introduction

Welcome to your second lesson on trees! In our previous session, we built a foundational vocabulary, defining key terms like root, parent, child, leaf, height, and depth. These concepts apply to all tree data structures.

Today, we'll narrow our focus to one of the most important and frequently-encountered types of trees in computer science and technical interviews: the Binary Search Tree (BST). As its name suggests, it's a special kind of binary tree that is optimized for searching.

Our goal is to understand the specific rules or properties that a tree must follow to be considered a Binary Search Tree. Mastering these properties is essential, as they are the reason BSTs are so efficient and form the basis for all operations you'll perform on them later.

From General Trees to Binary Trees

Before we can define a Binary Search Tree, we first need to understand what a Binary Tree is. The distinction is simple but fundamental. A general tree can have any number of children per node, but a binary tree has a strict limit.

Let's watch a short segment that clarifies this.

Binary Trees - Data Structures Explained

This video from Aaron Jack will first recap the general idea of a tree and then introduce the specific rule that defines a binary tree.

Watch from 01:19 to 03:28. Pay close attention to the one main rule that distinguishes a binary tree from other types of trees.

As you saw, the defining rule of a binary tree is straightforward:

Each node can have at most two children.

These children are typically referred to as the left child and the right child. This simple constraint is the first step toward the highly structured nature of a Binary Search Tree.

The Binary Search Tree Property

A Binary Search Tree is a binary tree that adds a crucial second rule regarding how the data (or keys) in the nodes are organized. This rule is known as the Binary Search Tree Property or the BST Invariant.

Let's look at a concise definition and a clear visual comparison.

Binary Search Tree(BST) - Programiz

The following resource from Programiz provides a simple, direct definition of the BST property, along with an excellent image that contrasts a valid BST with an invalid one.

Read the first part of the page, down to the image titled 'Binary Search Tree'. Focus on the two properties listed that separate a BST from a regular binary tree.

The resource highlights two conditions, which can be combined into one core property:

For any given node in a Binary Search Tree, all keys in its left subtree must be less than the node's key, and all keys in its right subtree must be greater than the node's key.

This property must hold true for every single node in the tree, not just the root. This creates a recursive structure of order throughout the entire tree.

This animated demonstration will make the recursive nature of this property very clear.

Binary Search Trees (BST) Explained in Animated Demo

This video provides a fantastic animated walkthrough of the BST property, emphasizing how it applies to entire subtrees, not just immediate children.

Watch from 01:18 to 02:02. Notice how the narrator checks the property for the root node against its entire left and right subtrees.

Visualizing Valid and Invalid BSTs

Let's solidify this concept with some clear examples.

Here is a classic, valid Binary Search Tree. Take a moment to trace it and confirm that the BST property holds for every node. For example, the root is 8. Everything in its left subtree (3, 1, 6, 4, 7) is less than 8, and everything in its right subtree (10, 14, 13) is greater than 8. Now, pick another node, like 6, and verify the property for its children.

Binary Search Tree Properties Illustration — A diagram illustrating a valid Binary Search Tree rooted at 8. The left subtree contains values less than 8, and the right subtree contains values greater than 8. This property holds recursively for all nodes in the tree.

Now, let's look at some examples that are not Binary Search Trees. Understanding why a tree fails the test is just as important as knowing what a valid one looks like.

Examples of Non-Binary Search Trees (No BSTs) — This image shows three different trees that violate the Binary Search Tree property. The first has duplicate values. The second has a value in the right subtree (7) that is smaller than its ancestor (8). The third has a value in the left subtree (9) that is larger than its parent (6).

Let's break down the violations shown in the image:

Duplicates: The first tree has two nodes with the value 4. Standard BSTs do not allow duplicate keys. (Some implementations might place duplicates in the right subtree, but for our purposes, we'll assume keys are unique).
Right Subtree Violation: In the second tree, the node 7 is in the right subtree of 8. Since 7 < 8, this violates the rule that all nodes in the right subtree must be greater.
Left Subtree Violation: In the third tree, the node 9 is in the left subtree of 6. Since 9 > 6, this violates the rule that all nodes in the left subtree must be smaller.

Deeper Dive into BST Properties

The primary BST property gives rise to several other interesting and useful characteristics. Understanding these will be helpful as you prepare for technical interviews, where you may be asked to compare data structures.

Binary Search Tree (BST) Introduction and Properties

This article from EnjoyAlgorithms provides a more formal list of BST properties and discusses their advantages compared to other data structures.

Read the sections 'Binary Search Tree (BST) Introduction and Properties' and 'Properties of binary search trees'. Pay special attention to properties 1 and 3, which highlight the key advantages of a BST.

Two particularly important consequences of the BST property mentioned in the article are:

Sorted Traversal: If you traverse the tree in a specific order (called an "in-order traversal," which we will cover later), you will visit the nodes in ascending sorted order. This makes BSTs a natural choice for maintaining sorted collections of data.
Efficient Operations: The BST property allows for fast searching. Because the data is ordered, you can eliminate half of the remaining tree at each step of a search, similar to how binary search works on a sorted array. This leads to an average search time of $O (lo g n)$ , which is a huge improvement over the $O (n)$ time required for an unsorted list.

Let's see a quick demonstration of how a search works. You don't need to worry about the implementation details yet, just focus on how the BST property guides the search.

Binary Trees - Data Structures Explained

This final clip from the Aaron Jack video demonstrates how the BST property allows us to efficiently search for a value.

Watch from 06:28 to 08:48. Notice how at each node, the decision to go left or right is determined by comparing the target value to the current node's value.

Self-Check

Examine the following three trees. For each one, determine if it is a valid Binary Search Tree. If it isn't, explain which node violates the BST property and why.

Tree 1:

Tree 2:

Tree 3:

Click here to see the answers

Tree 1: Valid BST. All nodes in the left subtrees are smaller than their parents, and all nodes in the right subtrees are larger. (e.g., for node 20, the left subtree has {10, 5, 15}, all < 20; the right subtree has {30}, > 20. This pattern holds for node 10 as well.)
Tree 2: Invalid BST. The node 60 violates the property. It is in the left subtree of 70 (which is correct, as 60 < 70), but it is also in the right subtree of the root 50. Since 60 > 50, it correctly belongs in the right subtree. However, the node 60 is the right child of 30, and 60 > 30, which is a direct violation of the rule for node 30.
Tree 3: Invalid BST. The node 6 violates the property. It is in the left subtree of the root 8. Therefore, all nodes in that subtree must be less than 8. While 3 is less than 8, its child 6 is also in the left subtree of 8. The problem is that 6 is the right child of 3, but 6 > 3, which is correct. The violation occurs at the root: 6 is in the left subtree of 8, but it is not smaller than all its ancestors on the path from the root. To be more precise, the chain 8 -> 3 -> 6 is the issue. 6 is a right child of 3 and that's fine. But 6 is in the left sub-tree of 8 and is not smaller than 8 (it is) so that's also fine. Wait, let me re-check. The rule is left < parent < right. For node 3, its right child is 6. 6 > 3, so this is valid. The issue is with a different node. Let's re-examine Tree 2, I think my explanation was a bit confusing.

Correction:

Tree 2: The violation is at node 30. Its right child is 60. The rule is that all nodes in the right subtree of a node must be greater than the node. 60 > 30, so this is locally correct. However, let's look at the root 50. The entire subtree rooted at 30 is its left subtree. Therefore, all nodes in that subtree must be less than 50. The node 60 is in the left subtree of 50, but 60 > 50. This is the violation. The global property is broken.
Tree 3: The violation is at node 3. Its right child is 6. This is locally valid since 6 > 3. But let's look at the root, 8. The node 6 is in the left subtree of 8. But 6 is not less than 3. Let's trace this again carefully. The rule is every node in the left subtree must be less than the parent. For root 8, the left subtree contains 3 and 6. 3 < 8 and 6 < 8. So far so good. Now check node 3. It has no left child. Its right child is 6. 6 > 3, which is also correct. Therefore, Tree 3 is a Valid BST. My initial analysis was incorrect, which highlights how important it is to check the rules carefully at every node!

Conclusion

In this lesson, we zeroed in on the specific rules that define a Binary Search Tree. This structure is not just a theoretical curiosity; it's a practical and powerful tool for managing and searching data efficiently.

Key Takeaways:

A Binary Tree is a tree where each node has at most two children (left and right).
A Binary Search Tree (BST) is a binary tree that also adheres to the BST property.
The BST Property: For any node, all keys in the left subtree are less than the node's key, and all keys in the right subtree are greater than the node's key.
This property must be true for every node in the tree, making it a recursive definition.
This ordered structure is what allows for efficient O(log n) search operations, which we will explore next.

Preview of the Next Lesson:

Now that you can identify a valid BST and understand the property that makes it powerful, it's time to put that property to use. In the next lesson, we will implement a search operation in a BST. You'll write your first piece of tree-related code, seeing exactly how the BST property guides the algorithm to find a value quickly.

Recommended resources