A sorted binary tree

In the trees so far, a value could be anywhere, so a search had to visit every node. A sorted binary tree (also called a binary search tree) keeps its values in order. Everything in a node's left subtree is smaller than the node's value, and everything in its right subtree is greater:

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

Searching

The order makes searching fast, in the same way as binary search. Compare the value you're looking for with the node's value. If it's smaller, it can only be in the left subtree, and if it's greater, only in the right one. So the search goes down one path and never needs the other side:

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


def find(node, value):
    if node is None:
        return False
    if value == node.value:
        return True
    if value < node.value:
        return find(node.left, value)
    return find(node.right, value)


tree = Node(50, Node(30, Node(20), Node(40)), Node(70, Node(60), Node(80)))
print(find(tree, 60))
print(find(tree, 65))

True
False

The search for 65 goes from 50 to the right, from 70 to the left, and from 60 to the right, where there's nothing: None gives False. It looked at three nodes out of seven. In a tree with a million values whose branches are about equally deep, it would look at about twenty.

Adding values

To add a value, go down the same path as a search. When the way on is None, that's the place for the new node:

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


def add(node, value):
    if value < node.value:
        if node.left is None:
            node.left = Node(value)
        else:
            add(node.left, value)
    elif value > node.value:
        if node.right is None:
            node.right = Node(value)
        else:
            add(node.right, value)


def print_in_order(node):
    if node is not None:
        print_in_order(node.left)
        print(node.value)
        print_in_order(node.right)


tree = Node(42)
for value in [17, 99, 8, 23, 61, 23]:
    add(tree, value)
print_in_order(tree)

8
17
23
42
61
99

A value that's already in the tree is neither smaller nor greater than the node that holds it, so neither branch adds it again: the second 23 is left out.

print_in_order visits the left subtree first, then the node, and then the right subtree. In a sorted tree, everything on the left is smaller and everything on the right is greater, so the values come out in increasing order.

The shape of the tree depends on the order the values are added in. Adding values that are already sorted, such as 1, 2, 3, 4, makes every new node a right child, and the "tree" becomes one long line. Searching it is then no faster than going through a list.