🎓 A1Learner
🔍

DSA The BST Property

A binary search tree is a binary tree with one ordering rule at every node. Every value in the left subtree is smaller, and every value in the right subtree is bigger.

The rule at one node

At the root of this small tree, the left value must be smaller and the right value bigger. The comparisons print as True.

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


root = TreeNode(8, TreeNode(3), TreeNode(10))
print("Left smaller:", root.left.value < root.value)
print("Right bigger:", root.right.value > root.value)

Inorder comes out sorted

The inorder walk from the traversals lesson runs on this BST. Its list is collected here, and the sorted check belongs to the points below.

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

def inorder(node, order):
    if node is None:
        return
    inorder(node.left, order)
    order.append(node.value)
    inorder(node.right, order)


tree = TreeNode(8,
                TreeNode(3, TreeNode(1), TreeNode(6)),
                TreeNode(10))
order = []
inorder(tree, order)
print("Inorder:", order)

Example

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

def inorder(node, order):
    if node is None:
        return
    inorder(node.left, order)
    order.append(node.value)
    inorder(node.right, order)


def contains(node, target):
    if node is None:
        return False
    if node.value == target:
        return True
    return contains(node.left, target) or contains(node.right, target)


bst = TreeNode(8,
               TreeNode(3, TreeNode(1), TreeNode(6)),
               TreeNode(10, None, TreeNode(14)))

other = TreeNode(8,
                 TreeNode(3, TreeNode(1), TreeNode(12)),
                 TreeNode(10, None, TreeNode(14)))

bst_order = []
inorder(bst, bst_order)
other_order = []
inorder(other, other_order)

print("BST inorder:", bst_order)
print("Comes out sorted:", bst_order == sorted(bst_order))
print("Other inorder:", other_order)
print("Comes out sorted:", other_order == sorted(other_order))
print("12 sits in the left subtree of 8:", contains(other.left, 12))
print("12 is bigger than 8:", 12 > other.value)

Key points

  • BST property: at every node, all left-subtree values are smaller and all right-subtree values are bigger
  • The rule binds the whole subtree, not only the two direct children
  • An inorder walk of a BST always reads in sorted order
  • BST values in this series are unique, so each value is strictly smaller or strictly bigger than the node

In this example, two trees share one shape and differ in a single value. The first tree obeys the ordering rule everywhere, and its inorder walk comes out sorted. The second tree places 12 under 3, which looks fine at that parent. But 12 sits in the left subtree of 8 while being bigger than 8. So the rule breaks, and the inorder walk stops being sorted.

Note

A plain binary tree has no ordering rule, so the property is extra structure on the same TreeNode class

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Which of these trees breaks the BST property?