# 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.

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

self.size = 0

# append at the end
def append(self, node):
while cur.next != None:
cur = cur.next
cur.next = node
self.size += 1

def size(self):
return self.size

def search(self, value):
found = False
if cur.data == value:
found = True
return cur
elif cur.next:
cur = cur.next
else:

def delete(self, value):
if cur.data == value:
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):
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.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.

{{#message}}{{{message}}}{{/message}}{{^message}}It appears your submission was successful. Even though the server responded OK, it is possible the submission was not processed. Please contact the developer of this form processor to improve this message. Learn More{{/message}}

Submitting…

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.

One-Time
Monthly
Yearly

#### 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

\$