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):
        self.data = data
        self.next = next
    
    def get_data(self):
        return self.data
    
    def set_data(self, new_data):
        self.data = new_data
    
    def get_next(self):
        return self.next

    def set_next(self, next_node):
        self.next = 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 cur.next != None:
            cur = cur.next
        cur.next = node
        self.size += 1
    
    def size(self):
        return self.size
    
    def search(self, value):
        cur = self.head
        found = False
        while not found:
            if cur.data == value:
                found = True
                return cur
            elif cur.next:
                cur = cur.next
            else:
                return ValueError("Value not found")
        
    def delete(self, value):
        cur = self.head
        if cur.data == value:
            self.head = cur.next
        else:
            while cur.data != value:
                cur = cur.next
            if cur.next:
                cur.data = cur.next.data
                cur.next = cur.next.next
            else:
                cur.next = None
                cur.data = None
                    

    def traverse(self):
        cur = self.head
        arr = [cur.data]
        while cur.next:
            cur = cur.next
            arr.append(cur.data)
        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()}")
ll.append(node2)
ll.append(node3)
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: {ll.search(10)}")
ll.append(node4)
ll.append(node5)
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: {ll.search(10)}")
ll.delete(2)
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):
        self.append(BinaryTree(val))

    def append(self, node):
        _val = node.val
        if _val <= self.val:
            if self.left:
                print(f"moving left to append {_val}")
                self.left.append(node)
            else:
                print(f"setting left {_val}")
                self.left = node
        else:
            if self.right:
                print(f"moving right to append {_val}")
                self.right.append(node)
            else:
                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:
            self.left.search(val)
        elif val > self.val and self.right:
            self.right.search(val)
        else:
            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)
        else:
            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
                else:
                    parent.right = successor.right
                # reset left and right nodes of the successor
                successor.left = self.left
                successor.right = self.right
                return successor
            else:
                if self.left:
                    return self.left
                else:
                    return self.right
        else:
            if self.val > val:
                if self.left:
                    self.left = self.left.delete(val)
            else:
                if self.right:
                    self.right = self.right.delete(val)
        return self
    
    def inorder_print(self):
        if self.left:
            self.left.inorder_print()
        print(self.val)
        if self.right:
            self.right.inorder_print()

root = BinaryTree(5)
root.inorder_print()
print('\n')
root.append_val(2)
root.append_val(8)
root.append_val(3)
root.inorder_print()
print('\n')
root.append_val(1)
root.append_val(10)
root.append_val(7)
root.inorder_print()
root = root.delete(5)
root.inorder_print()

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.

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

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

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly