Algorithms and Data Structures: Linked Lists and Binary Trees

For this tutorial, you’ll have to understand functions and classes. In this tutorial, we’ll go over linked lists and binary trees. Linked lists are an important Python Data Structure that consist of a head node, and other nodes being “linked” or pointed at by the node before it. Binary trees are used for hierarchical data, like a linked list, it starts with a head or root node and other nodes being linked or pointed at by the node before it, the key difference is that nodes in binary trees can point to two child nodes.

Python Linked List Implementation

There are two types of linked lists, singly linked lists and doubly linked lists. In this section we’ll just go over singly linked lists. I will cover doubly linked lists at a later date with more advanced data structures. Linked lists are a group of nodes which are all linked from the “root” or “parent” node with pointers. In a singly linked list, each node should contain a value and a pointer to a child node. If you do not already know how to declare Classes and Functions in Python I would recommend learning that first. I will create a post on it and link it in the future.

A simple implementation of a linked list should allow us to append a node, check the size of the list, search for a value, and delete a node. There are many ways to implement linked lists, this is simply one that I found to be most reasonable. Note that I also included a way to traverse the list for simpler printing.

class Node(object):
    def __init__(self, data=None, next=None): = data = next
    def get_data(self):
    def set_data(self, new_data): = new_data
    def get_next(self):

    def set_next(self, next_node): = next_node

class Linked_List(object):
    def __init__(self, head=None):
        self.head = head
        self.size = 0
    # append at the end
    def append(self, node):
        cur = self.head
        while != None:
            cur = = node
        self.size += 1
    def size(self):
        return self.size
    def search(self, value):
        cur = self.head
        found = False
        while not found:
            if == value:
                found = True
                return cur
                cur =
                return ValueError("Value not found")
    def delete(self, value):
        cur = self.head
        if == value:
            self.head =
            while != value:
                cur =
       = None
       = None

    def traverse(self):
        cur = self.head
        arr = []
            cur =
        return arr

node1 = Node(4)
node2 = Node(2)
node3 = Node(6)
node4 = Node(10)
node5 = Node(5)
ll = Linked_List(node1)
print(f"Current linked list is {ll.traverse()}")
print(f"After adding some nodes, we get {ll.traverse()}")
print(f"Now the size of the linked list is {ll.size}")
print(f"If we search for 10, we should see that it is not in the list: {}")
print(f"However if we append some nodes, and one of them has value 10 like: {ll.traverse()}")
print(f"We should now get a response for searching for 10: {}")
print(f"After deleting node 2, we get {ll.traverse()}")

Python Binary Tree Implementation

Here’s the thing about binary trees, they’re a broad topic. In theory, any structure with a root node and 0, 1, or 2 children per node could be a binary tree. In this Python implementation, we’re going to specifically go over a binary search tree. That means that our left nodes will be less than or equal to the root node, and our right nodes will be greater than the root node. Note that you can also implement a binary search tree that has right nodes that are greater than or equal to the root node, and left nodes that are less than the root node, but here we’ve chosen to include the equality condition on the left side just because we have to pick a side.

The example implementation of a Binary Tree in Python shows how we can append a value, search by value, delete by value, and print an in-order traversal of our binary tree. An in-order traversal is a traversal in which the root node is “visited” in-between its left and right nodes. In our case, it should show the numbers we added to the tree in numerical order.

# val is the value of the node
# right is the right node
# left is the left node
class BinaryTree(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def append_val(self, val):

    def append(self, node):
        _val = node.val
        if _val <= self.val:
            if self.left:
                print(f"moving left to append {_val}")
                print(f"setting left {_val}")
                self.left = node
            if self.right:
                print(f"moving right to append {_val}")
                print(f"setting right {_val}")
                self.right = node
    def search(self, val):
        if val == self.val:
            return True
        if val <= self.val and self.left:
        elif val > self.val and self.right:
            print("Value could not be found")
            return False
    # returns the parent node and the successor
    def find_successor(self, parent):
        if self.left:
            return self.left.find_successor(self)
            return parent, self
    def delete(self, val):
        print(f"Deleting {val} if it exists")
        if self.val == val:
            if self.right and self.left:
                parent, successor = self.right.find_successor(self)
                # split out the successor
                if parent.left == successor:
                    parent.left = successor.right
                    parent.right = successor.right
                # reset left and right nodes of the successor
                successor.left = self.left
                successor.right = self.right
                return successor
                if self.left:
                    return self.left
                    return self.right
            if self.val > val:
                if self.left:
                    self.left = self.left.delete(val)
                if self.right:
                    self.right = self.right.delete(val)
        return self
    def inorder_print(self):
        if self.left:
        if self.right:

root = BinaryTree(5)
root = root.delete(5)

That’s it for the second installation of a tutorial on Data Structures in Python. There are more tutorials available on the site for self-learners. There will be a post on more advanced Tree structures coming soon.

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.

Yujian Tang