Binary Search Trees

Beakal Tiliksew, Karleigh Moore, Caleb Rash, and contributed

Binary Search Trees (also binary trees or BSTs) contain sorted data arranged in a tree-like structure. A binary tree consists of "root" and "leaf" data points, or nodes, that branch out in two directions.

Binary trees store "items" (such as numbers, names, etc.) in memory, allowing fast lookup, addition, and removal of items. They can be used to implement either dynamic sets of items or lookup tables that allow finding an item by its key. Binary trees and related variations have many practical uses such as in databases, for parsing syntax in a programming language, and in file compression.

Overview
Operations
Tree Shape and Balancing

Overview

Each tree starts with a single root node that contains data as well as references to left and right nodes. Each left and right node can also contain data and references to its own left and right nodes, respectively. This pattern continues recursively, forming a tree.

Binary tree diagram

Operations

All of the code examples in this section are using a common class for the nodes of the binary tree:

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value # information that is being stored in the tree
        self.left = left   # the left child (subtree)
        self.right = right # the right child (subtree)

    def __str__(self):
        return node.value

Tree traversal

There are two primary ways to traverse, or iterate through, a tree: depth-first and breadth-first. In the depth-first method, the left subtree is searched first, then the right subtree is searched. In the breadth-first method, the search progresses through the nodes at each height level of the tree, or in other words, the root node first, then level 1 nodes, then level 2 nodes, and so forth.

Depth-first

def b_list_depth_first(node):
    if not node:
        return []
    result = []
    if node.left:
        # append the left subtree's values
        result = result + b_list_depth_first(node.left)
    if node.value:
        # append this node's value
        result.append(node.value)
    if node.right:
        # append the right subtree's values
        result = result + b_list_depth_first(node.right)
    return result

Breadth-first

def b_list_breadth_first(node):
    result = []
    nodelist = [node]
    # nodelist contains the nodes for height n
    while nodelist:
        # next_nodelist will contain the nodes for height n+1
        next_nodelist = []
        for subnode in nodelist:
            # append the current node's value to the result list
            result.append(subnode.value)
            # append the current node's children to next_nodelist
            if subnode.left:
                next_nodelist.append(subnode.left)
            if subnode.right:
                next_nodelist.append(subnode.right)
        nodelist = next_nodelist

    return result

Insertion

To insert a node, find the leftmost leaf node that is less than the value being inserted. Add a child node to that node containing the inserted value.

The method for inserting a new value

def b_insert(node, value):
    if not node.value:
        node.value = value
    if value < node.value:
        node.left = node.left or Node()
        b_insert(node.left, value)
    elif value > node.value:
        node.right = node.right or Node()
        b_insert(node.right, value)

Deletion

Deletion is less straightforward. There are three cases to consider:

Case 1: If the deleted node has no children, remove the node from its parent.
Case 2: If the deleted node has one child, replace the node with its child.
Case 3: If the deleted node has two children:
1. Start with the current node's right child
2. Find that child's leftmost child
3. Replace the current node's value with the leftmost child's value
4. Call the deletion function on the current node's right child

def b_delete(node, value, parent=None):
    if not node:
        return
    elif value < node.value:
        b_delete(node.left, value, parent=node)
    elif value > node.value:
        b_delete(node.right, value, parent=node)
    else:
        # CASE 1: remove the node from its parent
        if not node.left and not node.right:
            if parent.left and node == parent.left:
                parent.left = None
            else:
                parent.right = None

        # CASE 3: two children...
        elif node.left and node.right:
            successor = node.right
            successor_parent = node
            while successor.left:
                successor_parent = successor
                successor = successor.left
            node.value = successor.value
            b_delete(successor, successor.value, parent=successor_parent)

        # CASE 2: replace the node with its child
        else:
            if parent.left and node == parent.left:
                if node.left:
                    parent.left = node.left
                if node.right:
                    parent.left = node.right
            else:
                if node.left:
                    parent.right = node.left
                if node.right:
                    parent.right = node.right

Tree Shape and Balancing

Inserting and deleting nodes in a binary tree affects the shape of the tree, and the shape of a tree can affect the efficiency of operations on the tree. A "balanced" tree has the smallest possible height, or node depth, and is the most efficient configuration for the tree for the set of all possible searches.

In the example below, both trees contain the same data, but only one is balanced:

Since the efficiency of operations is proportional to the height of the tree, binary trees must be periodically rebalanced to maintain efficiency. Some variations of binary trees, such as red-black trees, AVL trees, and scapegoat trees, are self-balancing, in that when a node is inserted or deleted, the tree is modified to improve its shape.

Cite as: Binary Search Trees. Brilliant.org. Retrieved from https://brilliant.org/wiki/binary-search-trees/

Binary Search Trees

Relevant For...

Contents

Overview

Operations

Tree traversal

Insertion

Deletion

Tree Shape and Balancing

Waste less time on Facebook — follow Brilliant.

Excel in math and science

Master concepts by solving fun, challenging problems.

It's hard to learn from lectures and videos

Learn more effectively through short, conceptual quizzes.

Our wiki is made for math and science

Master advanced concepts through explanations, examples, and problems from the community.

Used and loved by 4 million people

Learn from a vibrant community of students and enthusiasts, including olympiad champions, researchers, and professionals.

Relevant For...

Contents

Tree traversal

Insertion

Deletion

Excel in math and science

Master concepts by solving fun, challenging problems.

It's hard to learn from lectures and videos

Learn more effectively through short, conceptual quizzes.

Our wiki is made for math and science

Master advanced concepts through explanations, examples, and problems from the community.

Used and loved by 4 million people

Learn from a vibrant community of students and enthusiasts, including olympiad champions, researchers, and professionals.

Master advanced concepts through explanations,
examples, and problems from the community.

Learn from a vibrant community of students and enthusiasts,
including olympiad champions, researchers, and professionals.

Master advanced concepts through explanations,
examples, and problems from the community.

Learn from a vibrant community of students and enthusiasts,
including olympiad champions, researchers, and professionals.