Writing a Binary Search Tree in Python – With Examples
Tags: python, computerscience, languages, mailinglist
Published: 2021-01-22 03:44:45

---
title: Writing a Binary Search Tree in Python – With Examples
published: true
date: 2021-01-12 14:06:35 UTC
tags: Python,ComputerScience,Languages,MailingList
canonical_url: https://qvault.io/2021/01/12/binary-search-tree-in-python/
---

 ![lone tree unsplash](https://qvault.io/wp-content/uploads/2021/01/lone-tree-unsplash.jpg "lone tree unsplash")

The post [Writing a Binary Search Tree in Python – With Examples](https://qvault.io/2021/01/12/binary-search-tree-in-python/) first appeared on [Qvault](https://qvault.io).

A binary search tree, or BST for short, is a tree whose nodes each store a key greater than all their left child nodes and less than all of their right child nodes. Binary trees are useful for storing data in an organized way, which allows for it to be fetched, inserted, updated, and deleted quickly. The greater-than and less-than ordering of nodes mean that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the number of nodes in the tree.

To be precise, binary search trees provide an average Big-O complexity of `O(log(n))` for retrieval, insertion, update, and delete operations. Log(n) is much faster than the linear `O(n)` time required to find items in an unsorted array. Many popular production databases such as PostgreSQL and MySQL use binary trees under the hood to speed up CRUD operations.

![Binary Search Tree](https://qvault.io/wp-content/uploads/2021/01/bst.jpg "bst")<figcaption>BST</figcaption>

## Step 1 – BSTNode Class

Our implementation won’t use a `Tree` class, but instead just a `Node` class. Binary trees are really just a pointer to a root node that in turn connects to each child node, so we’ll run with that idea.

First, we create a constructor:

```python
class BSTNode:
    def  __init__ (self, val=None):
        self.left = None
        self.right = None
        self.val = val
```

We’ll allow a value (key) to be provided, but if one isn’t provided we’ll just set it to `None`. We’ll also initialize both children of the new node to `None`.

## Step 2 – Insert

We need a way to insert new data. The insert method is as follows:

```python
def insert(self, val):
        if not self.val:
            self.val = val
            return

        if self.val == val:
            return

        if val < self.val:
            if self.left:
                self.left.insert(val)
                return
            self.left = BSTNode(val)
            return

        if self.right:
            self.right.insert(val)
            return
        self.right = BSTNode(val)
```

If the node doesn’t yet have a value, we can just set the given value and return. If we ever try to insert a value that also exists, we can also simply return as this can be considered a `noop`. If the given value is less than our node’s value and we already have a left child then we recursively call `insert` on our left child. If we don’t have a left child yet then we just make the given value our new left child. We can do the same (but inverted) for our right side.

## Step 3 – Get Min and Get Max

```python
def get_min(self):
        current = self
        while current.left is not None:
            current = current.left
        return current.val

def get_max(self):
        current = self
        while current.right is not None:
            current = current.right
        return current.val
```

`getMin` and `getMax` are useful helper functions, and they’re easy to write! They are simple recursive functions that traverse the edges of the tree to find the smallest or largest values stored therein.

## Step 4 – Delete

```python
def delete(self, val):
        if self == None:
            return self
        if val < self.val:
            self.left = self.left.delete(val)
            return self
        if val > self.val:
            self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return selfdef delete(self, val):
        if self == None:
            return self
        if val < self.val:
            if self.left:
                self.left = self.left.delete(val)
            return self
        if val > self.val:
            if self.right:
                self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return selfdef delete(self, val):
        if self == None:
            return self
        if val < self.val:
            self.left = self.left.delete(val)
            return self
        if val > self.val:
            self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return self
```

The delete operation is one of the more complex ones. It is a recursive function as well, but it also returns the new state of the given node after performing the delete operation. This allows a parent whose child has been deleted to properly set it’s `left` or `right` data member to `None`.

## Step 5 – Exists

The exists function is another simple recursive function that returns `True` or `False` depending on whether a given value already exists in the tree.

```python
def exists(self, val):
        if val == self.val:
            return True

        if val < self.val:
            if self.left == None:
                return False
            return self.left.exists(val)

        if self.right == None:
            return False
        return self.right.exists(val)
```

## Step 6 – Inorder

It’s useful to be able to print out the tree in a readable format. The `inorder` method print’s the values in the tree in the order of their keys.

```python
def inorder(self, vals):
        if self.left is not None:
            self.left.inorder(vals)
        if self.val is not None:
            vals.append(self.val)
        if self.right is not None:
            self.right.inorder(vals)
        return vals
```

## Step 7 – Preorder

```python
def preorder(self, vals):
        if self.val is not None:
            vals.append(self.val)
        if self.left is not None:
            self.left.preorder(vals)
        if self.right is not None:
            self.right.preorder(vals)
        return vals
```

## Step 8 – Postorder

```python
def postorder(self, vals):
        if self.left is not None:
            self.left.postorder(vals)
        if self.right is not None:
            self.right.postorder(vals)
        if self.val is not None:
            vals.append(self.val)
        return vals
```

## Usage

```python
def main():
    nums = [12, 6, 18, 19, 21, 11, 3, 5, 4, 24, 18]
    bst = BSTNode()
    for num in nums:
        bst.insert(num)
    print("preorder:")
    print(bst.preorder([]))
    print("#")

    print("postorder:")
    print(bst.postorder([]))
    print("#")

    print("inorder:")
    print(bst.inorder([]))
    print("#")

    nums = [2, 6, 20]
    print("deleting " + str(nums))
    for num in nums:
        bst.delete(num)
    print("#")

    print("4 exists:")
    print(bst.exists(4))
    print("2 exists:")
    print(bst.exists(2))
    print("12 exists:")
    print(bst.exists(12))
    print("18 exists:")
    print(bst.exists(18))
```

## Full Binary Search Tree in Python

```python
class BSTNode:
    def  __init__ (self, val=None):
        self.left = None
        self.right = None
        self.val = val

    def insert(self, val):
        if not self.val:
            self.val = val
            return

        if self.val == val:
            return

        if val < self.val:
            if self.left:
                self.left.insert(val)
                return
            self.left = BSTNode(val)
            return

        if self.right:
            self.right.insert(val)
            return
        self.right = BSTNode(val)

    def get_min(self):
        current = self
        while current.left is not None:
            current = current.left
        return current.val

    def get_max(self):
        current = self
        while current.right is not None:
            current = current.right
        return current.val

    def delete(self, val):
        if self == None:
            return self
        if val < self.val:
            if self.left:
                self.left = self.left.delete(val)
            return self
        if val > self.val:
            if self.right:
                self.right = self.right.delete(val)
            return self
        if self.right == None:
            return self.left
        if self.left == None:
            return self.right
        min_larger_node = self.right
        while min_larger_node.left:
            min_larger_node = min_larger_node.left
        self.val = min_larger_node.val
        self.right = self.right.delete(min_larger_node.val)
        return self

    def exists(self, val):
        if val == self.val:
            return True

        if val < self.val:
            if self.left == None:
                return False
            return self.left.exists(val)

        if self.right == None:
            return False
        return self.right.exists(val)

    def preorder(self, vals):
        if self.val is not None:
            vals.append(self.val)
        if self.left is not None:
            self.left.preorder(vals)
        if self.right is not None:
            self.right.preorder(vals)
        return vals

    def inorder(self, vals):
        if self.left is not None:
            self.left.inorder(vals)
        if self.val is not None:
            vals.append(self.val)
        if self.right is not None:
            self.right.inorder(vals)
        return vals

    def postorder(self, vals):
        if self.left is not None:
            self.left.postorder(vals)
        if self.right is not None:
            self.right.postorder(vals)
        if self.val is not None:
            vals.append(self.val)
        return vals
```

## Thanks For Reading!

Take [computer science courses on our new platform](https://app.qvault.io/)

Follow and hit us up on Twitter [@q\_vault](https://twitter.com/q_vault) if you have any questions or comments

[Subscribe](https://mailchi.mp/5c7f5c281bbe/qvault-newsletter-subscribe) to our Newsletter for more programming articles

## Related Reading

- [Building a Linked List in Python](https://qvault.io/2021/01/11/building-a-linked-list-in-python-with-examples/)