BST basics, insert and search in Python

Why it matters

Finding one value in a long list means checking the items one by one until you hit it. A binary search tree (BST) lets you throw away half of the remaining values at every step, the same way a dictionary lets you find a word without reading the whole book. Sorted sets and sorted maps in most languages are built on this idea, so the code you write in this lesson is the foundation for the rest of the module.

By the end of this lesson you will be able to build a tree from numbers, search it, find its smallest and largest values, and explain why the shape of the tree decides how fast each step is.

Start with the problem

Suppose you store the numbers 20, 30, 40, 50, 60, 70 and 80 in a plain list. You want to know whether 65 is in it. The only safe method is to look at every item. With 7 items that is 7 checks. With a million items it is a million checks, and you still do not know where to put a new number so the list stays in order.

Now suppose the same numbers are arranged so that each number knows where its smaller neighbours and its larger neighbours are. Start at the middle. If the number you want is smaller, you only need to look in the lower half. If it is larger, you only need the upper half. Each check removes about half of what is left. That idea, repeated, is what a binary search tree gives you.

A tree is a way to link values together. Here is the vocabulary you need, in plain words:

• A node is one box that holds a value and two links.
• A link (also called a reference) is a note that says which other node comes next. In Python a link is a variable that holds an object.
• The root is the top node. It has no parent.
• A child is a node that a node links to. A node with two children has a left child and a right child.
• A leaf is a node with no children.
• A subtree is any node together with everything below it. Each child starts its own subtree.
• A binary tree is a tree where every node has at most two children.
• The height is the number of nodes on the longest path from the root down to a leaf. A single node has height 1. An empty tree has height 0. This course counts height this way so that the formulas stay simple.

A plain binary tree has no order. Its left and right children can hold any values. A binary search tree adds one rule, and that rule is what makes search fast.

The BST rule

A binary search tree is a binary tree where, for every node:

• every value in its left subtree is smaller than the node,
• every value in its right subtree is larger than the node.

The rule applies at every node, not only at the root. It also applies to whole subtrees, not only to direct children. That detail matters a lot, and a later section shows a tree that breaks it in a sneaky way.

Here is a tree that follows the rule. Read it as: 50 is the root, 30 and 70 are its children, and so on.

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

Check one node by hand. Node 30 has 20 and 40 below it. 20 is smaller than 30 and 40 is larger, so the rule holds there. Check the root too. Every value on the left (20, 30, 40) is smaller than 50. Every value on the right (60, 70, 80) is larger than 50. The rule holds for the whole tree.

In this course a BST holds no duplicates. If you insert a value that is already in the tree, the tree stays the same. You will see why this choice matters when you write code.

An everyday analogy

Think of a row of numbered lockers that someone has already sorted. If you want locker 65 and you stand at locker 50, you know it is not on the left, so you do not walk to the left side. You only need to decide between "go right" and "found it". A BST works like that row, except the path to each locker is stored as links instead of as positions in a row.

Search, step by step

Search means: given a target value, find out whether it is in the tree. Start at the root. At each node, do one of three things:

1. If the node's value equals the target, you found it. Stop.
2. If the target is smaller than the node's value, move to the left child.
3. If the target is larger, move to the right child.
4. If there is no child in the direction you need to go, the target is not in the tree. Stop.

Let us trace search for 60 in the tree above.

Three nodes were visited. The tree has seven nodes, so a plain list would have needed up to seven checks. In a list you might check every item. In the tree you checked three.

Now trace search for 65.

The search ends with no child to move to, so 65 is not in the tree. Three nodes were visited again. The walk always follows one path from the root down, so the number of steps is at most the height of the tree.

Search is a binary search in disguise

Look at the sorted list 20, 30, 40, 50, 60, 70, 80 and search for 60 the way you would in a sorted list. The middle value is 50 (index 3). 60 is larger, so you look at the right half, 60, 70, 80. The middle of that half is 70. 60 is smaller, so you look at the left part, which is just 60. Found.

The three middle values you checked were 50, 70 and 60. Those are exactly the nodes you visited in the tree. A BST stores the midpoints of a binary search as links, so you can insert and delete without moving every value, which a sorted list cannot do cheaply.

Step through the animation above. Watch how each check cuts the range in half and how the same three midpoints appear again in the tree. When the range is down to a single value, the search either finds it or gives up.

Python: a node and a tree

Python has no built-in tree type. You build one from a class. A class is a blueprint for objects. An object is a bundle of named values (called attributes) plus functions that work on them. A node needs three attributes: a value, a left link and a right link.

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

Let us read each part.

• class TreeNode: defines a new type called TreeNode. Each call like TreeNode(42) creates one object of that type.
• def __init__(self, val): is the constructor. Python runs it right after you create an object. The name __init__ is special, and the two underscores on each side are part of the name.
• self is the object being built. It is the first parameter of every method in the class, and Python fills it in for you. You never pass it yourself. Inside the method, self.val means "the val attribute of this node".
• self.left = None and self.right = None set both links to None. None is Python's word for "no object here". It plays the role that null plays in Java.

When you write TreeNode(30), Python creates an object, runs __init__, and gives you back a reference to that object. An empty tree is simply a variable that holds None. A tree with one node is a variable that refers to that node, whose left and right are both None.

Python has no separate type for small whole numbers. An integer such as 30 is an object, and it can be as large as memory allows. This means you never need to think about a value overflowing, which Java programmers have to watch for. The lesson on validation returns to this point.

What happens in memory

Imagine the memory as a long street of numbered houses. Each TreeNode is one house. Inside the house are three labelled boxes: val, left and right. The left box does not hold a house's contents. It holds the number (the address) of another house, or it is None. So a tree is a set of houses that point at each other.

When you run root = insert(root, 50) on an empty tree, Python creates the house for 50 and stores its address in the variable root. Every other node is reached by following addresses from there. If you lose the address of the root, you lose the whole tree, because nothing else points to it. This is why the root is always kept in a variable.

Python passes objects by reference, which has one effect that surprises beginners. A function gets its own copy of the variable, but both copies point at the same object. Changing an attribute of the object is seen by everyone. Assigning a new object to the copy is not seen by the caller. The next section relies on this.

Insert, step by step

Insert means: add a value so that the BST rule still holds. The insertion walk is the same as the search walk. You go left or right at each node until you fall off the tree. The place where you fall off is where the new node belongs.

Let us insert 65 into the tree from the previous section.

1. Start at 50. 65 is larger, so go right to 70.
2. At 70, 65 is smaller, so go left to 60.
3. At 60, 65 is larger, and the right link is None. This is where you fall off.
4. Create a new node for 65 and link it as the right child of 60.

The tree now has 65 as the right child of 60. The rule still holds: 65 is larger than 60, which is its parent, and smaller than 70, which is the ancestor where we turned left. Every ancestor check passes.

The recursive version

Recursion means a function that calls itself on a smaller problem. Insert is a natural fit: "to insert into a tree, insert into the left or right subtree, and then the tree is still a tree". Here is the recursive version.

def insert(root, v):
    if root is None:
        return TreeNode(v)
    if v < root.val:
        root.left = insert(root.left, v)
    elif v > root.val:
        root.right = insert(root.right, v)
    return root

Read it one line at a time.

• If the tree is empty (root is None), the tree becomes one new node holding v. The function returns that node.
• If v is smaller, the function inserts v into the left subtree. The result of that call is stored back into root.left.
• If v is larger, the same happens on the right.
• If v equals root.val, nothing happens. This is how duplicates are ignored.
• The function returns root, so the caller also knows which node is at the top of this subtree.

Use is None to test for None, not == None. is asks whether two names point at the same object, which is the right question for None.

The line root.left = insert(root.left, v) is the most important line in the lesson. It does two jobs at once. Most of the time, insert returns the same node it was given, so root.left = root.left changes nothing. When root.left was None, insert returns a brand-new node, and that assignment is what links the new node into the tree.

What happens inside the call stack

When you call a function, Python keeps a small record for that call. The record stores the arguments and the place to return to. These records are kept in a region called the call stack, which works like a stack of plates: you add a plate on top when you call and remove it when the function returns.

Here is what happens when you insert 10 into the tree 50, 30, 70, 20, 40, 60, 80. The walk goes down four calls deep.

1. insert(50, 10) runs. 10 is smaller, so it calls insert(30, 10) and waits.
2. insert(30, 10) runs. 10 is smaller, so it calls insert(20, 10) and waits.
3. insert(20, 10) runs. 10 is smaller, so it calls insert(None, 10) and waits.
4. insert(None, 10) runs. The root is None, so it creates a node for 10 and returns it.
5. Back in insert(20, 10): the result (the new node) is stored in root.left. So node 20 now has a left child, 10. The function returns node 20.
6. Back in insert(30, 10): the result (node 20) is stored in root.left, which is the same node as before. Nothing changes. It returns node 30.
7. Back in insert(50, 10): the same thing. It returns node 50, which is the root.

Four plates were on the stack at the deepest point. The stack grows by one plate for each level you go down, so the depth of the call stack equals the height of the tree. That is why a very tall tree can crash a recursive function, which you will see in the common mistakes section.

Building the seven-node tree one value at a time

Seeing the whole tree at once hides the process. Build it on paper instead, and draw the tree after every insert. This is the habit that catches bugs before they reach the computer.

Insert the values 50, 30, 70, 20, 40, 60 and 80, in that order. Each drawing below shows the tree after one insert.

After inserting 50, the tree is one node. The root is 50, and both links are empty.

50

Inserting 30 is smaller than 50, so 30 goes to the left. The tree is now 50 with a left child 30.

    50
   /
 30

Inserting 70 is larger than 50, and the right link of 50 is empty, so 70 becomes the right child.

    50
   /  \
 30    70

Inserting 20 starts at 50. It is smaller, so it goes left to 30. It is smaller than 30, and the left link of 30 is empty, so 20 becomes the left child of 30. Nothing else changes, and the tree now has three levels on the left.

Inserting 40 starts at 50, goes left to 30, and then goes right, because 40 is larger than 30. The right link of 30 is empty, so 40 becomes the right child of 30.

Inserting 60 starts at 50, goes right to 70, and then goes left, because 60 is smaller than 70. The left link of 70 is empty, so 60 becomes its left child.

Inserting 80 starts at 50, goes right to 70, and then goes right, because 80 is larger than 70. The right link of 70 is empty, so 80 becomes its right child. This leaves the complete seven-node tree from the start of the lesson.

Each insert looked at the path from the root and changed exactly one empty link. No existing node moved. That is the main reason insert is fast: the rest of the tree is never rewritten.

Now try the same values in a different order: 20, 30, 40, 50, 60, 70, 80. The first insert makes 20 the root. Each of the next six values is larger than all the ones before it, so each one goes to the right. The result is a chain of seven nodes with height 7, which looks like this:

20
  \
   30
     \
      40
        \
         50
           \
            60
              \
               70
                 \
                  80

The same seven values now need up to seven comparisons to search, instead of three. Keep this chain in mind. The cost section and the balancing lesson both return to it.

What a search does when the value is missing

A search that fails is just as important as one that succeeds, because many programs use the failed search to decide what to do next. Search for 45 in the seven-node tree. You go 50 (45 is smaller, so left), 30 (45 is larger, so right), 40 (45 is larger, and the right link of 40 is None). The search stops with no node. Three nodes were visited, and the answer is "not present".

The same walk tells you where 45 would go if you inserted it. It would become the right child of 40. Insert and search use the same path, so a single helper that returns the last node visited is useful in many problems. Later lessons use this idea to find the closest value in a tree, and to find the value that comes just before or after a missing one.

If the tree is empty, the search starts with None, so the loop never runs and the answer is "not present" straight away. Insert into an empty tree is also simple: the new node becomes the root. These two cases are the bottom of every recursive BST function, which is why they appear first in the code.

Running the first program

Here is a complete program. It builds the tree from seven values, prints the values in sorted order, and runs two searches and the min and max functions. You do not need to type anything in the Input box.

Its output is:

20 30 40 50 60 70 80
True
False
20 80

The search function is the loop version. It uses a while loop instead of recursion, which means it uses only one variable (node) and no extra calls. The line node = node.left if target < node.val else node.right is the walk in one line. The form a if condition else b means "if the condition is true, use a, otherwise use b".

The min_value function follows left links until the next one is None. The smallest value is always the leftmost node. The max_value function does the same with right links.

Python does not need a separate TreeNode class for each tree. The same class holds any number of nodes, and each node only knows about its own two links.

Walking the tree in order

The inorder function collects the values in sorted order. It visits the left subtree first, then the node itself, then the right subtree. Because every value on the left is smaller and every value on the right is larger, the list is sorted.

The order in which you visit the nodes matters. The three standard orders are:

• Preorder: node, left, right. Good for copying a tree.
• Inorder: left, node, right. Gives sorted order for a BST.
• Postorder: left, right, node. Good for deleting a tree from the bottom up.

Step through the walk below. Watch which node is visited at each step, and compare the inorder list with the sorted list of values.

Look at the walk for the inorder order. It goes all the way down the left side first, records 20, comes back up to record 30, then walks the right side of 30, which is 40. Only after that is 50 recorded. The pattern repeats. The result is the same as sorting the values, without using a sort.

The inorder function appends to a list it was given, instead of returning a new list each time. Lists are mutable, so every recursive call adds to the same list. Returning new lists at every level works too, but it creates many small lists for no benefit.

Reading input and tracing a search

The first program used fixed values. Real programs usually read their data. The next program reads a list of numbers and a target, and prints the path the search walked. Tracing the path is a useful debugging habit: it shows you exactly which nodes the search looked at.

The input format is: one line with n, the count of values; one line with the n values; and one line with the target. For example, to insert the seven values and search for 60, type:

7
50 30 70 20 40 60 80
60

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def insert(root, v):
    if root is None:
        return TreeNode(v)
    if v < root.val:
        root.left = insert(root.left, v)
    elif v > root.val:
        root.right = insert(root.right, v)
    return root
 
 
# Walks down from the root and records every node it visits.
def search_path(node, target):
    path = []
    while node is not None:
        path.append(str(node.val))
        if target == node.val:
            return "path: " + " ".join(path) + " -> found"
        node = node.left if target < node.val else node.right
    return "path: " + " ".join(path) + " -> not found"
 
 
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
n = int(input())
values = input().split()
target = int(input())
 
root = None
for text in values[:n]:
    root = insert(root, int(text))
 
sorted_values = []
inorder(root, sorted_values)
print("sorted:", " ".join(str(v) for v in sorted_values))
print(search_path(root, target))

With that input, the output is:

sorted: 20 30 40 50 60 70 80
path: 50 70 60 -> found

Change the target to 65 and the path becomes 50 70 60, followed by -> not found. The walk stopped because the right link of 60 was None. This is the first debugging skill you can practise: compare the path the program printed with the path you traced on paper. If they differ, the bug is either in the tree you built or in the comparison.

input() reads one line of text and returns it without the line break. Its result is always a string, so int(...) turns a number written as text into a whole number. input().split() cuts a line at its spaces and returns a list of strings. Each value in that list is still text until you convert it.

The line " ".join(...) joins a list of strings with a single space between them. It is the usual way to print a list of values on one line. The str(v) inside the generator turns each number into text first, because join only accepts strings.

Cost: the shape decides the speed

Every search, insert, min and max walks one path from the root down, so each costs time proportional to the height h. The time is written O(h). The letter O (big O) describes how the work grows as the input grows. You will study it properly in the complexity module. For now, read O(h) as "the number of nodes on one path".

The height depends on the order in which you inserted the values. Compare two trees built from the same seven numbers, 1 to 7.

In the balanced tree, each comparison removes about half of the values, so the height is about log2(n). For seven values that is 3. In the chain, every value is larger than all the values before it, so every insert goes to the right. The tree becomes a list with extra links, and search is no faster than a plain list.

Here is the same experiment as a program. It reads values, builds the tree and prints the height.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def insert(root, v):
    if root is None:
        return TreeNode(v)
    if v < root.val:
        root.left = insert(root.left, v)
    elif v > root.val:
        root.right = insert(root.right, v)
    return root
 
 
def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))
 
 
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
n = int(input())
values = input().split()
 
root = None
for text in values[:n]:
    root = insert(root, int(text))
 
out = []
inorder(root, out)
print("inorder:", " ".join(str(v) for v in out))
print("height:", height(root))

Type 7 on the first line and 1 2 3 4 5 6 7 on the second. The output is:

inorder: 1 2 3 4 5 6 7
height: 7

Now type 7 and then 4 2 6 1 3 5 7. The output is:

inorder: 1 2 3 4 5 6 7
height: 3

The sorted output is identical in both runs. Only the height differs, and the height is what decides how fast every operation is. This is the most important idea in the module. A BST is only fast when it is balanced. Lesson 4 of this module shows how to keep it balanced.

The height function uses recursion. The height of a tree is 1 plus the larger of the heights of its two subtrees. An empty tree has height 0, which is the stopping case. max is a built-in function that returns the larger of its arguments.

Insert without recursion

Recursion is elegant, but a loop works too, and a loop does not add one call per level. It also gives you a clear place to report whether a value was added. The next program inserts with a loop. It keeps track of a cur variable that moves down the tree, and it stops when it finds a None link to fill.

Python cannot change the caller's variable from inside a function (the reference section explained why). So the loop version lives inside a small class. The class holds the root in an attribute, self.root, and the method changes that attribute. This is a common Python pattern: when a function needs to replace the top of a structure, the structure gets its own object to hold the top.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
class BST:
    def __init__(self):
        self.root = None
 
    # Returns True if a new node was added, False if the value was already there.
    def insert(self, v):
        if self.root is None:
            self.root = TreeNode(v)
            return True
        cur = self.root
        while True:
            if v == cur.val:
                return False
            if v < cur.val:
                if cur.left is None:
                    cur.left = TreeNode(v)
                    return True
                cur = cur.left
            else:
                if cur.right is None:
                    cur.right = TreeNode(v)
                    return True
                cur = cur.right
 
 
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
 
n = int(input())
values = input().split()
 
tree = BST()
added = 0
ignored = 0
for text in values[:n]:
    if tree.insert(int(text)):
        added += 1
    else:
        ignored += 1
 
out = []
inorder(tree.root, out)
print(f"added {added}, ignored {ignored} duplicates")
print(" ".join(str(v) for v in out))

Type 8 and then 50 30 70 30 20 70 40 80. The output is:

added 6, ignored 2 duplicates
20 30 40 50 70 80

The second 30 and the second 70 found an equal value on the way down and returned False without changing the tree. Count the output carefully: 8 values in, 6 added, 2 ignored, and the inorder list has 6 values.

The line print(f"added {added}, ignored {ignored} duplicates") is an f-string. The f before the quote tells Python to put the values of the variables inside the braces into the text. Braces are only special inside an f-string, so the code above is safe.

Common mistakes

Most beginner bugs with BSTs fall into a few groups. Each one below shows a real message or a real symptom, so you can recognise it quickly.

Mistake 1: forgetting self in a method. Methods inside a class take self as their first parameter. If you leave it out, Python still calls the method with the object, and the count of arguments is wrong. Here is a class with self missing:

class BST:
    def insert(v):
        return v
 
t = BST()
t.insert(5)

Python reports:

TypeError: BST.insert() takes 1 positional argument but 2 were given

The message says the method accepts one argument, but two were given. The two are the object and the value 5. The fix is to write def insert(self, v):. Read the message from the end of the first line: "2 were given" tells you the object was passed in, and the method has no place for it.

Mistake 2: not assigning the result of the recursive call. This runs without any error message, and it is the most common logic bug in insert:

def insert(root, v):
    if root is None:
        return TreeNode(v)
    if v < root.val:
        insert(root.left, v)          # result thrown away
    elif v > root.val:
        insert(root.right, v)
    return root

Run the program that prints the inorder walk with this version, using the seven values 50, 30, 70, 20, 40, 60, 80. The output is:

[50]

Only the root is in the list. The new nodes were created, but nothing linked them in, so they are lost. The fix is to write root.left = insert(root.left, v) and root.right = insert(root.right, v). A good habit is to check the result of any function that might create or replace a node.

Mistake 3: calling min or max on an empty tree. If the root is None, the function reads node.left and fails. Python reports:

AttributeError: 'NoneType' object has no attribute 'left'

The first part names the type of error: an attribute was read from an object that does not have it. NoneType is the type of None. The second part says which attribute was read, left. Python does not print the line number in this short form, but the traceback above the message shows the line. The fix is to check for None before calling min_value, and say what an empty tree should return.

Mistake 4: deep recursion on a chain. Python limits how deep the call stack may grow. The limit is 1000 by default, and you can read it with sys.getrecursionlimit(). On the machine where this lesson was checked, the recursive insert built a chain of 990 values, and failed on the chain of 1000. The failure looks like this:

RecursionError: maximum recursion depth exceeded

The exact number depends on the machine and the Python build, so yours may fail at a different size. The limit is a safety rule. Python stops a function that calls itself too many times, instead of letting the computer run out of memory. The loop version of insert from the previous section builds the same chain without error, because it makes no nested calls. A recursive inorder walk over a chain of that length fails in the same way, so long chains need loops, or a higher limit set with sys.setrecursionlimit(). Raising the limit only moves the crash point, so the loop is the better fix.

Mistake 5: expecting O(log n) from a sorted insert order. Inserting 1 to 100 in order makes a chain of height 100. Each search takes 100 steps. This is correct behaviour for a BST, not a bug, but it surprises people who expect the fast cost. Lesson 4 of this module shows the cure.

Mistake 6: expecting a change to a variable inside a function to reach the caller. Here is a function that tries to give the caller a new root:

def set_root(root):
    root = TreeNode(99)
 
x = None
set_root(x)
print(x)

The output is:

None

The function assigned a new object to its own copy of the name root. The caller's x still holds None. Changing an attribute of an object would have worked, but replacing the variable does not. This is why the loop version of insert lives in a class and stores the root in self.root.

Debugging walkthrough

Suppose a program prints 20 30 40 50 60 70 80 for the seven values, but your search for 60 returns False. Here is a method that works for any BST bug.

1. Print the structure, not only the answer. Use the inorder walk. If it prints sorted values, the tree has all the nodes. If it prints fewer values than you inserted, the insert is losing nodes, as in mistake 2.
2. Print the search path. The search_path program above shows every node the walk visited. Compare that list with the tree you drew on paper. The first node that does not match is where the decision went wrong.
3. Check the comparison direction. Write the comparison as a sentence: "target is less than node value, so go left". A reversed < and > makes every search go the wrong way.
4. Check the links after each insert. For a small tree, draw it after each insert. Five inserts take a minute to draw and save an hour of guessing.

When you apply this method to the broken version from mistake 2, step 1 already shows the problem. The inorder walk prints one value, not seven. The inserted values were never linked. Steps 2 and 3 are not needed once you see the missing links.

Use print(node.val, node.left is None, node.right is None) inside a loop when you want to see the state of one node at a time. Printing a whole object shows only its address in memory, such as <__main__.TreeNode object at 0x7f...>, and that address is different on every run.

Variations and edge cases

Real BST code has to handle a few special cases. Think about each one before you write your own version.

• The empty tree. insert on None makes a new root. search returns False. min and max have nothing to return, so they must be guarded.
• One node. The root is also the leaf, the minimum and the maximum at once.
• Negative numbers. The rule works for any values that can be compared. Negative numbers go left of positive ones in the usual way.
• Duplicates. This course ignores them, as the programs above do. Some applications store duplicates in the right subtree or keep a count in each node. Decide the policy before you write the code, and test it with a repeated value.
• Sorted or nearly sorted input. The chain problem from the cost section. Ask whether the input could be sorted before you trust the speed.
• Large values. Python integers have no fixed size limit, so a value such as 10 ** 30 is stored and compared exactly. A language with fixed-size integers would need to check for overflow instead.

Real-world and interview uses

Ordered data appears in many systems. A database index is often a balanced tree, so that a lookup by a key does not scan the table. Python's standard library has no sorted set or sorted map built on a tree. A dictionary keeps keys in the order they were added, not in sorted order, and a list with the bisect module gives fast searches but slow inserts in the middle. Third-party packages offer sorted containers when you need both fast inserts and sorted order.

Interviewers ask BST questions because they check three things at once. Can you keep the rule while changing the tree? Can you walk the tree in the right order? Can you explain the cost? A good answer states the rule in one sentence, shows the walk on a small tree, and says that the cost is O(h), which is O(log n) only when the tree is balanced. If you can add that the worst case is O(n), you have covered the most common follow-up question.

Practice

1. Insert 10, 5, 15, 3 and 7 into an empty BST by hand and draw the result. Hint: 3 and 7 are both below 5, one on each side.

        10
      /    \
    5       15
   / \
  3   7

2. Count the nodes visited when you search for 40 and for 65 in the sample tree of this lesson. Hint: include the node where the search stops, and not the None link.

3. Write a recursive function search_rec(node, target) that returns True or False. Hint: the same three cases as the loop version, with the recursive call on the child you chose.

def search_rec(node, target):
    if node is None:
        return False
    if target == node.val:
        return True
    if target < node.val:
        return search_rec(node.left, target)
    return search_rec(node.right, target)

4. Write size(node) that returns the number of nodes. Hint: an empty tree has size 0, and a node has size 1 plus the sizes of its two subtrees.

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

5. Write height(node) using the rule from this lesson, where a single node has height 1. Check it on the balanced seven-node tree, which should give 3. Hint: the same shape as size, with max instead of +.

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

6. Predict the output of inserting the values 5, 3, 8, 3, 9 with the BST class, then printing the inorder walk with " ".join. Hint: one of the values is a duplicate.

7. Write find_node(root, target) that returns the node holding the value, or None if it is absent. Hint: the search code is the same, but return the node instead of True.

def find_node(root, target):
    cur = root
    while cur is not None and cur.val != target:
        cur = cur.left if target < cur.val else cur.right
    return cur

8. You insert the values 1 to 15 in increasing order into an empty BST. What is the height, and how many nodes does a search for 15 visit? Hint: every new value goes to the right of the one before.

9. Write min_or_minus_one(root) that returns the smallest value, and returns -1 for the empty tree. Hint: check for None before reading any attribute.

def min_or_minus_one(root):
    if root is None:
        return -1
    cur = root
    while cur.left is not None:
        cur = cur.left
    return cur.val

10. A balanced tree holds 1000 values. Roughly how many nodes does a successful search visit in the worst case? Hint: the height of a balanced tree is about log2 of the number of nodes, and log2 of 1000 is a little under 10.

What you now know

• A BST keeps every smaller value on the left and every larger value on the right, at every node and in every subtree.
• Search and insert walk one path from the root, so their cost is O(h), the height.
• Insert ends by linking a new node where a None link was found. Writing root.left = insert(root.left, v) is what makes the link stick.
• The inorder walk prints the values in sorted order, so it is the first check to run when a tree looks wrong.
• The same values can make a short tree or a long chain, depending on the insert order. The shape decides the speed.