1. Concept library
  2. Data Structures & Algorithms
  3. Module 9: Trees

Concept

Binary search trees

A binary search tree keeps every left descendant smaller and every right descendant larger than a node, so search, insert and delete walk one path of O(height). An inorder traversal yields sorted order.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain the ordering rule and why search walks one path
  2. Insert and search in a BST and explain the cost in terms of height
  3. Spot the validation that only checks a node against its children

In practice

A few lines that show Binary search trees doing its job.

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

def is_bst(node, lo=float("-inf"), hi=float("inf")):
    if node is None: return True
    return (lo < node.value < hi and is_bst(node.left, lo, node.value)
            and is_bst(node.right, node.value, hi))

The common mistake

Watch for

Validating a BST by checking each node only against its direct children. A grandchild can violate the ordering while every parent-child pair looks fine; the check needs the bounds inherited from above.

What to know first

Your roadmap puts these before Binary search trees, unless you already know them.

How it stays learned

Once a session shows you understand Binary search trees, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled

Where it leads

Topics that build on Binary search trees.

Previous in the module← Tree traversals
Next in the moduleLowest common ancestor →