Python Binary Search Tree

Python Binary Search Tree

A Tree is any data structure that follows some particular rules. The tree must have exactly one root node. If you have two root nodes, what you actually have is two trees. One tree has one root, and one root equals one tree. Additionally, each node can have any number of child nodes or may have zero children, in which case we call that node a leaf. A node can have 100 children or more and still be a valid tree. Each node, except for the root, links to exactly one parent. If you have a child with two parents, then loops get introduced and cause all kinds of problems. A node cannot be its own parent. If your data structure meets these criteria, then it is a tree.

About Trees

binary search tree
There are many different types of trees with additional rules that make them useful. Oftentimes each node in a tree usually has some kind of data associated with it. Think of the DOM in web development or a directory structure within an operating system. In our case, we’ll be talking about the binary search tree. In a binary search tree, each node has only two children called a left and a right child. This is what makes it a binary(two) tree. Each node has a value associated with it. Values to the left of the node must be less than the value of their parents. Values to the right of the node must be greater than the value of their parents. BSTs may not equal values, each value must be unique.

Building A Tree

The code below implements a tree via the Node class. This is a basic building block of our trees. We can pass some data to it when it’s initialized. Each node will have a number that the node represents. In addition to the Node, we have some data and properties of left and right children. With the basic structure implemented, we then start building a tree. We can attach new nodes to the left and right of our parent node. So node.left equals node 15, node.right equals 25. Note that I’m putting nodes with smaller data, in this case, the 15 to the left and I’m putting nodes with larger data, in this case, the 25 to the right. This is because we’re building a binary search tree and smaller values always go to the left, larger values go to the right. Expanding the tree a little more, we set node.left.left equals 12 and that’s going to be our smallest number in the tree. Node.left.right is set to 16. Node.right.left is set to 23. Node.right.right is set to 100. Then you can see how we are able to access values at any point in the tree.

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


class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name


node = Node(20)

node.left = Node(15)
node.right = Node(25)

node.left.left = Node(12)
node.left.right = Node(16)

node.right.left = Node(23)
node.right.right = Node(100)

nice_tree = Tree(node, 'A real nice Tree.')

print(nice_tree.name)
print(nice_tree.root.data)
print(nice_tree.root.left.data)
print(nice_tree.root.right.right.data)
A real nice Tree.
20
15
100

How To Search A Tree

In this section, we can add search to the tree knowing that small values always go to the left and the large values always go to the right. The search method is going to take in a target, which is the data that we’re looking for in the tree. The first thing we’re going to do is check if the current node matches the target that we’re searching for. If self.data equals target, then we found what we were looking for. By returning the node that we found in the tree, we can stop the search. Otherwise, if no match is found, we need to keep looking. We do this by recursively checking the left and right sides of the tree.

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

    def search(self, target):
        if self.data == target:
            print("Found the value!")
            return self

        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("Value is not in tree")


class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def search(self, target):
        return self.root.search(target)


node = Node(20)

node.left = Node(15)
node.right = Node(25)

node.left.left = Node(12)
node.left.right = Node(16)

node.right.left = Node(23)
node.right.right = Node(100)

nice_tree = Tree(node, 'A real nice Tree')

result = nice_tree.search(23)
if result:
    print(f'{result.data} is in the "{nice_tree.name}" tree')
Found the value!
23 is in the "A real nice Tree" tree

How To Traverse A Tree

Three common algorithms to traverse a tree include Traverse In Order, Traverse Pre Order, and Traverse Post Order. You can read the specifics of how they work at the links cited. The code for our implementation is below.

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

    def search(self, target):
        if self.data == target:
            print("Found it!")
            return self

        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("Value is not in tree")

    def traversePreorder(self):
        print(self.data)
        if self.left:
            self.left.traversePreorder()
        if self.right:
            self.right.traversePreorder()

    def traverseInorder(self):
        if self.left:
            self.left.traverseInorder()
        print(self.data)
        if self.right:
            self.right.traverseInorder()

    def traversePostorder(self):
        if self.left:
            self.left.traversePostorder()
        if self.right:
            self.right.traversePostorder()
        print(self.data)


class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def search(self, target):
        return self.root.search(target)


node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)

node.traversePreorder()
print('-' * 20)
node.traverseInorder()
print('-' * 20)
node.traversePostorder()
20
15
12
16
25
23
100
--------------------
12
15
16
20
23
25
100
--------------------
12
16
15
23
100
25
20

Get The Max Height

The height of a tree is how many nodes there are from the root to the leaf at the deepest part of the tree. The height of a tree is its maximum height. The height is important because it determines the maximum run time for the search of a tree. To find the maximum height of a tree is done with a small recursive function shown here.

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

    def search(self, target):
        if self.data == target:
            print("Found it!")
            return self

        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("Value is not in tree")

    def height(self, h=0):
        leftHeight = self.left.height(h + 1) if self.left else h
        rightHeight = self.right.height(h + 1) if self.right else h
        return max(leftHeight, rightHeight)


class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def search(self, target):
        return self.root.search(target)

    def height(self):
        return self.root.height()


node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)

print(node.height())
2

Get Nodes From A Given Depth

In this section, we have a function that takes in an arbitrary depth, like two, and prints out the nodes at that depth from left to right. This is a useful thing to have if you want to print out the entire contents of the tree.

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

    def traversePreorder(self):
        print(self.data)
        if self.left:
            self.left.traversePreorder()
        if self.right:
            self.right.traversePreorder()

    def traverseInorder(self):
        if self.left:
            self.left.traverseInorder()
        print(self.data)
        if self.right:
            self.right.traverseInorder()

    def traversePostorder(self):
        if self.left:
            self.left.traversePostorder()
        if self.right:
            self.right.traversePostorder()
        print(self.data)

    def search(self, target):
        if self.data == target:
            print("Found it!")
            return self

        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("Value is not in tree")

    def getNodesAtDepth(self, depth, nodes=[]):
        if depth == 0:
            nodes.append(self.data)
            return nodes

        if self.left:
            self.left.getNodesAtDepth(depth - 1, nodes)
        else:
            nodes.extend([None] * 2 ** (depth - 1))

        if self.right:
            self.right.getNodesAtDepth(depth - 1, nodes)
        else:
            nodes.extend([None] * 2 ** (depth - 1))
        return nodes

    def height(self, h=0):
        leftHeight = self.left.height(h + 1) if self.left else h
        rightHeight = self.right.height(h + 1) if self.right else h
        return max(leftHeight, rightHeight)


class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def traverseInorder(self):
        self.root.traverseInorder()

    def traversePreorder(self):
        self.root.traversePreorder()

    def traversePostorder(self):
        self.root.traversePostorder()

    def search(self, target):
        return self.root.search(target)

    def getNodesAtDepth(self, depth):
        return self.root.getNodesAtDepth(depth)

    def height(self):
        return self.root.height()


node = Node(20)
node.left = Node(15)
node.right = Node(25)
node.left.left = Node(12)
node.left.right = Node(16)
node.right.left = Node(23)
node.right.right = Node(100)

print(node.getNodesAtDepth(0))
print(node.getNodesAtDepth(1))
print(node.getNodesAtDepth(2))
[20]
[20, 15, 25]
[20, 15, 25, 12, 16, 23, 100]

Printing A Tree

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

    def traversePreorder(self):
        print(self.data)
        if self.left:
            self.left.traversePreorder()
        if self.right:
            self.right.traversePreorder()

    def traverseInorder(self):
        if self.left:
            self.left.traverseInorder()
        print(self.data)
        if self.right:
            self.right.traverseInorder()

    def traversePostorder(self):
        if self.left:
            self.left.traversePostorder()
        if self.right:
            self.right.traversePostorder()
        print(self.data)

    def search(self, target):
        if self.data == target:
            print("Found it!")
            return self

        if self.left and self.data > target:
            return self.left.search(target)

        if self.right and self.data < target:
            return self.right.search(target)

        print("Value is not in tree")

    def getNodesAtDepth(self, depth, nodes=[]):
        if depth == 0:
            nodes.append(self.data)
            return nodes

        if self.left:
            self.left.getNodesAtDepth(depth - 1, nodes)
        else:
            nodes.extend([None] * 2 ** (depth - 1))

        if self.right:
            self.right.getNodesAtDepth(depth - 1, nodes)
        else:
            nodes.extend([None] * 2 ** (depth - 1))
        return nodes

    def height(self, h=0):
        leftHeight = self.left.height(h + 1) if self.left else h
        rightHeight = self.right.height(h + 1) if self.right else h
        return max(leftHeight, rightHeight)


class Tree:
    def __init__(self, root, name=''):
        self.root = root
        self.name = name

    def _nodeToChar(self, n, spacing):
        if n is None:
            return '_' + (' ' * spacing)
        spacing = spacing - len(str(n)) + 1
        return str(n) + (' ' * spacing)

    def print(self, label=''):
        print(self.name + ' ' + label)
        height = self.root.height()
        spacing = 3
        width = int((2 ** height - 1) * (spacing + 1) + 1)
        # Root offset
        offset = int((width - 1) / 2)
        for depth in range(0, height + 1):
            if depth > 0:
                # print directional lines
                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\'] * (2 ** (depth - 1))))
            row = self.root.getNodesAtDepth(depth, [])
            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))
            spacing = offset + 1
            offset = int(offset / 2) - 1
        print('')

    def traverseInorder(self):
        self.root.traverseInorder()

    def traversePreorder(self):
        self.root.traversePreorder()

    def traversePostorder(self):
        self.root.traversePostorder()

    def search(self, target):
        return self.root.search(target)

    def getNodesAtDepth(self, depth):
        return self.root.getNodesAtDepth(depth)

    def height(self):
        return self.root.height()


tree = Tree(Node(20))
tree.root.left = Node(15)
tree.root.right = Node(25)
tree.root.left.left = Node(12)
tree.root.left.right = Node(16)
tree.root.right.left = Node(23)
tree.root.right.right = Node(100)

tree.print()
      20  
   /     \
  15      25      
 / \     / \
12  16  23  100 

Python Binary Search Tree Summary

In this tutorial, we learned about binary trees and reviewed some useful applications of this data structure. A binary tree is a tree data structure made up of nodes with at most two children. Each node can have a right and left child. The node at the top is referred to as the root node. A node without children is known as a leaf node. Most applications use different types of binary trees such as tries, binary search trees, and B-trees. In computer science, binary trees are often used for searching and sorting since they provide a means to store data hierarchically. Common operations that can be used on binary trees include insertion, deletion, and traversal.