ADT Binary Tree

You have already met the linked list, where each node points to one next node, making a straight line. A binary tree changes one thing: each node may point to two nodes — a left child and a right child. That single change turns a line into a branching shape, like a family tree drawn upside down.

The version you must know is the ordered binary tree (also called a binary search tree). It follows one rule whenever a value is added: anything smaller than a node goes into its left branch, anything larger goes into its right branch. Because the data is sorted by that rule as it is inserted, finding a value later means you can throw away half the tree at every step — which is exactly why trees are fast to search.

By the end of this page you will be able to draw a tree as values arrive, build the Node and BinaryTree classes, insert and find values, and explain why reading the tree “in order” prints everything sorted.

Picture the tree below. Mehrin enters these student marks one at a time into the revision tracker: 50, 30, 70, 20, 40, 60. The first value, 50, becomes the root. After that, every new value starts at the root and turns left (smaller) or right (larger) until it finds an empty spot, where it settles as a new leaf.

class Node:
    def __init__(self, data):
        self.data  = data       # the value stored
        self.left  = None       # left child (smaller)
        self.right = None       # right child (larger)

class BinaryTree:
    def __init__(self):
        self.root = None        # empty tree

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)          # first value becomes the root
        else:
            self._insert(self.root, value)

    def _insert(self, current, value):
        if value < current.data:              # smaller -> go left
            if current.left is None:
                current.left = Node(value)
            else:
                self._insert(current.left, value)
        else:                                 # larger (or equal) -> go right
            if current.right is None:
                current.right = Node(value)
            else:
                self._insert(current.right, value)

Read the _insert method as a sentence: “if the value is smaller than this node, deal with the left side; otherwise deal with the right side.” Each time, if the branch is empty (None) we drop the new node there; if not, we ask the same question one node further down. That “ask the same question further down” is recursion.

Tracing an insert means walking from the root and writing down each decision. Below, Aymaan inserts 45 into the tree from Section 2.

def find(self, target):
    current = self.root
    while current is not None:
        if target == current.data:
            return True                    # found it
        elif target < current.data:
            current = current.left         # smaller -> left subtree
        else:
            current = current.right        # larger -> right subtree
    return False                           # fell off the tree -> not present

Each comparison lets you ignore an entire subtree, so on a well-shaped tree you check far fewer than every node. The loop ends two ways: a match (True), or running off the bottom into None (False).

In-order means: for any node, first deal with its left subtree, then visit the node itself, then its right subtree. Because left always holds smaller values, you naturally print from smallest to largest.

def in_order(self, node):
    if node is not None:
        self.in_order(node.left)        # 1. left subtree
        print(node.data, end=" ")       # 2. this node
        self.in_order(node.right)       # 3. right subtree

# In-order traversal of 50, 30, 70, 20, 40, 60 produces:
# 20 30 40 50 60 70  -- sorted ascending!

Each node is a record: Data, LeftPointer, RightPointer. A RootPointer stores the index of the root; a FreePointer tracks the next unused slot. The null pointer is -1 (or 0 if the array starts at 1). Below is the tree 50, 30, 70 stored this way.

RootPointer = 0. Node 0 (the root, 50) points left to index 1 (30) and right to index 2 (70). Both 30 and 70 are leaves (their pointers are -1).

Fifteen exam-style tasks. Click Hint for bullet-point guidance, then Help to reveal a worked Python/pseudocode solution.