This Binary Search Trees lesson is for a beginner. Read the short notes, run each example, then change one name or number and run it again.
In a binary search tree, every value in the left subtree is smaller than the node, and every value in the right subtree is larger.
Search starts at the root and goes left or right. It does not scan every node.
Example 1: Start here
A tree that is inserted in sorted order becomes a line, and the search is no longer fast.
class Node: # a template for objects
def __init__(self, value, left=None, right=None): # runs when you create the object
self.value = value # store this on the object
self.left = left # store this on the object
self.right = right # store this on the object
root = Node(8, Node(3), Node(10)) # one object
found = root # another name for the same value
target = 10 # a whole number
while found and found.value != target: # keep repeating while this stays true
found = found.right if target > found.value else found.left # use the value before if when the test is true
print(found.value)
Example 2: Walk the values
Binary Search Trees starts by visiting one value at a time. Read the printed lines from top to bottom.
values = [9, 3, 11, 7] # a list; the values stay in this order
for value in values: # repeat the indented lines once per value
print(value)
Example 3: Keep the largest
Many data-structure lessons reduce a list to one answer. This one remembers the largest number seen so far.
values = [9, 3, 11, 7] # a list; the values stay in this order
best = values[0] # the first value
for value in values: # repeat the indented lines once per value
if value > best: # run the indented lines only when this is true
best = value # another name for the same value
print(best)
Example 4: Search for a target
A search asks one yes-or-no question: is the target in the collection? Binary Search Trees builds on that question.
values = [3, 9, 11] # a list; the values stay in this order
target = 9 # a whole number
print(target in values) # in is True when the value is found
