BST property and invariant in Data Structures Theory - Full Explanation

Introduction

Imagine you have a collection of numbers and want to organize them so you can quickly find any number later. Without a clear rule, searching can take a long time. The Binary Search Tree (BST) property and invariant solve this by keeping the numbers in a special order that makes searching fast and easy.

Explanation

BST Property

The BST property means that for every node in the tree, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger. This rule applies to every node, not just the root. It creates a sorted structure that helps in quick searching, insertion, and deletion.

Every node's left children are smaller, and right children are larger, maintaining order.

BST Invariant

The BST invariant is the rule that the BST property must always hold true after any operation like adding or removing nodes. This means the tree must be adjusted if needed to keep the order intact. Maintaining this invariant ensures the tree remains efficient for searching.

The BST property must be preserved after every change to keep the tree organized.

Real World Analogy

Think of a library where books are arranged so that all books with titles starting with letters before 'M' are on the left shelves, and those starting with letters after 'M' are on the right shelves. Every shelf follows this rule, so you can quickly find a book by checking the correct side.

BST Property → Library shelves where books on the left have titles alphabetically before a certain letter, and books on the right have titles after that letter

BST Invariant → The rule that the library must keep this arrangement after adding or removing books to ensure quick finding

Diagram

Diagram

        ┌─────10─────┐
       /             \
    ┌─5─┐           ┌─15─┐
   /     \         /      \
  2       7      12       20

A binary search tree where left children are smaller and right children are larger than their parent nodes.

Key Facts

Binary Search Tree (BST) → A tree data structure where each node has at most two children and follows the BST property.

BST Property → All nodes in the left subtree have smaller values, and all nodes in the right subtree have larger values than the parent node.

BST Invariant → The rule that the BST property must hold true after every insertion or deletion.

Left Subtree → The subtree containing nodes with values smaller than the parent node.

Right Subtree → The subtree containing nodes with values larger than the parent node.

Code Example

Data Structures Theory

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(self.root, value)

    def _insert(self, current, value):
        if value < current.value:
            if current.left is None:
                current.left = Node(value)
            else:
                self._insert(current.left, value)
        else:
            if current.right is None:
                current.right = Node(value)
            else:
                self._insert(current.right, value)

    def inorder(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.inorder(node.left, result)
            result.append(node.value)
            self.inorder(node.right, result)
        return result

# Example usage
bst = BST()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(7)
bst.insert(2)
print(bst.inorder(bst.root))

Common Confusions

Believing the BST property only applies to the root node.

Believing the BST property only applies to the root node. The BST property applies to every node in the tree, ensuring order throughout all subtrees.

Thinking the BST invariant is optional after insertions or deletions.

Thinking the BST invariant is optional after insertions or deletions. The BST invariant must always be maintained to keep the tree efficient and correctly ordered.

Summary

The BST property keeps all left children smaller and right children larger than their parent nodes.

The BST invariant ensures this property is maintained after every change to the tree.

Maintaining these rules allows fast searching, insertion, and deletion in the tree.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. All nodes have exactly two children.

B. Nodes are arranged in a circular linked list.

C. Left child nodes are smaller, right child nodes are larger than the parent node.

D. Each node stores a unique key with no order.

Solution

1. Step 1: Understand BST node arrangement

   A BST arranges nodes so that left children have smaller values and right children have larger values than their parent node.

2. Step 2: Compare options with BST definition

   Left child nodes are smaller, right child nodes are larger than the parent node. correctly states this property. Other options describe different or incorrect structures.

3. Final Answer:

   Left child nodes are smaller, right child nodes are larger than the parent node. -> Option C

4. Quick Check:

   BST property = left < parent < right [OK]

Hint: Remember BST means left smaller, right larger [OK]

Common Mistakes:

• Thinking all nodes must have two children
• Confusing BST with other tree types
• Ignoring the order property in BST

2. Which of the following is the correct way to check if a node's left child maintains the BST property?

easy

A. left_child.value > node.value

B. left_child.value < node.value

C. left_child.value == node.value

D. left_child.value >= node.value

Solution

1. Step 1: Recall BST left child rule

   In a BST, the left child's value must be less than the parent's value.

2. Step 2: Match this rule to options

   left_child.value < node.value correctly states left_child.value < node.value. Other options violate this rule.

3. Final Answer:

   left_child.value < node.value -> Option B

4. Quick Check:

   Left child < parent [OK]

Hint: Left child must be smaller than parent [OK]

Common Mistakes:

• Using greater than or equal instead of less than
• Allowing equal values on left child
• Confusing left and right child rules

3. Given the BST below, what is the correct in-order traversal output?

      10
     /  \
    5    15
   / \     \
  3   7     20

medium

A. [3, 5, 7, 10, 15, 20]

B. [10, 5, 3, 7, 15, 20]

C. [20, 15, 10, 7, 5, 3]

D. [5, 3, 7, 10, 15, 20]

Solution

1. Step 1: Understand in-order traversal

   In-order traversal visits left subtree, then node, then right subtree, producing sorted order in BST.

2. Step 2: Traverse the tree in-order

   Left subtree of 10: nodes 3, 5, 7 in order; then 10; then right subtree 15, 20.

3. Final Answer:

   [3, 5, 7, 10, 15, 20] -> Option A

4. Quick Check:

   In-order traversal = sorted nodes [OK]

Hint: In-order traversal of BST gives sorted list [OK]

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Listing nodes in insertion order
• Reversing the traversal order

4. Consider the following BST insertion code snippet. What is the error?

def insert(node, value):
    if node is null:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

medium

A. The code does not handle duplicate values correctly.

B. The base case for node is incorrect.

C. The recursive calls do not update the tree.

D. The function does not return the updated node.

Solution

1. Step 1: Analyze duplicate handling in insertion

   The code inserts duplicates into the right subtree without restriction, which may violate BST uniqueness if duplicates are not allowed.

2. Step 2: Check other parts of the code

   Base case and recursive updates are correct; function returns updated node properly.

3. Final Answer:

   The code does not handle duplicate values correctly. -> Option A

4. Quick Check:

   Duplicates need special handling in BST insert [OK]

Hint: Check how duplicates are treated in insertion [OK]

Common Mistakes:

• Assuming duplicates are automatically handled
• Ignoring return statements in recursion
• Confusing base case with recursive case

5. You want to verify if a binary tree is a valid BST. Which approach correctly checks the BST property for all nodes?

hard

A. Check if the tree has unique values only.

B. Check if the tree is balanced and has no cycles.

C. Check if each node's left child is smaller and right child is larger, recursively.

D. Check if all left descendants are smaller and all right descendants are larger than the node, using min and max limits.

Solution

1. Step 1: Understand BST validation requirements

   Each node must satisfy that all nodes in its left subtree are smaller and all in right subtree are larger, not just immediate children.

2. Step 2: Evaluate approaches

   Check if all left descendants are smaller and all right descendants are larger than the node, using min and max limits. uses min and max limits to ensure all descendants satisfy BST property, which is correct. Check if each node's left child is smaller and right child is larger, recursively. only checks immediate children, which is insufficient.

3. Final Answer:

   Check if all left descendants are smaller and all right descendants are larger than the node, using min and max limits. -> Option D

4. Quick Check:

   BST validation requires range checks, not just immediate children [OK]

Hint: Use min/max limits to validate BST recursively [OK]

Common Mistakes:

• Checking only immediate children values
• Confusing BST property with tree balance
• Assuming unique values guarantee BST