Linked lists & Binary Trees

Photo by Joshua Fuller on Unsplash

Linked Lists and Binary Trees are an essecial part of programming. As these data structures make our code run a lot faster and gives us more capabilities. The best example of this would be an autocomplete function, in which you put in the first few letters of a word, and are given a suggestion as to what word it thinks you might be typing. If this was done with a regular array of letters as opposed to a Binary Tree, then the run time would be unbarible. You would be waiting a long time for a suggestion that not only might be wrong, but will take away from the rest of your computers efficiency. As a coder, we love efficiency! So lets waste no time on introductions and jump right into how to build one, and how they work!

Linked Lists and Binary Trees are made up of one very important element known as a Node. A Node is kinda like a bucket that holds our information inside of it, along with instructions as how to get to it’s next destination. Linked List and Binary Trees are not built in functions of python, unlike dictionaries and arrays. So we will have to build our own using class objects.

#!python3#Node example
class Node():
def __init__(self, data):
self.data = data
self.pointer = None
node1 = Node('1')

Nodes can contain multiple pointers, and in a Double Linked List require directions for both the next node and before it. We can set those directions to assign the order of our Linked List as seen below. The code below goes over how to build a Double Linked List and some of it’s basic methods.

#!python3#Double Linked list example
class Node():
def __init__(self, data):
self.data = data
self.next = None
self.previous = None
class double_ll(object):
def __init__(self):
self.head = None
self.tail = None
# creates our linked list methods
def append(self, item):
# creates a node to add to the END of our list
new_node = Node(item)
# Check if this linked list is empty
if self.head is None:
# Assign head to new node
self.head = new_node
# sets previous to none, as it is the beggining of the list
new_node.previous = None
# Otherwise set previous as tail & insert new node after tail
else:
new_node.previous = self.tail
self.tail.next = new_node
# Update tail to new node regardless
self.tail = new_node
def prepend(self, item):
# Create a new node to add to the BEGINNING of our list
new_node = Node(item)
if self.head is None: # if empty make head new node
self.head = new_node
self.tail = new_node
else: # otherwise set new node to head
new_node.next = self.head
new_node.previous = None
self.head = new_node
def delete_from_tail(self):
# Delete the last item in the linked list
current = self.head
# Searches for the end of our double linked list
while current != None:
if current.next == self.tail:
break
# focus on the node right before the tail
current = current.next
"""you can't really delete items in a linked list so we remove access to it completely, and therefore have removed it from the list"""
current.next = None
current.previous = None
self.tail = current
def delete_from_head(self):
second = self.head.next
second.previous = None
self.head = sencond

""" And becuase we have created a double link list, we can traverse through it forwards and backwards! """
def forward_print(self):
current = self.head
while current != None:
print(current.data)
current = current.next

def backward_print(self):
current = self.tail
while current != None:
print(current.data)
current = current.previous

Despit Double Linked Lists being a bit more work to make, they can be very useful! Learning how to create Linked Lists can help you create stacks and queues for recursive functions. “But Anthony!”, I hear you asking, “what’s the difference between a Single Linked List and a Double?”. Simply put, a Single Linked List has only one direction it’s going in, while a Double Linked List goes both ways. I drew a demonstration below (sorry for the sloppy handwriting).

Linked List Double V Single by yours truly

The circles represent our nodes, that are holding ints as data. The node.next defines the next node’s objects id in our list, which helps our list find it’s way to our second node -which is holding the data of 2. A node.previous is added, as to go the other direction in our Double Linked List. Just as the tail points to None, so will our node.previous when at the beginning of the list.

The second reason I explained a Double ll, rather than a Single, is because we can use two different directions to our advantage -when creating a Binary Tree. There is no .next or .previous attribute. However, there is a .left and .right attribute. We will use these in order to build our tree, and give or nodes instructions on where we would like it to go. So grab some tea and take a deep breath before jumping into our next large section of code.

#!python3# Binary Tree Example
class Node:
def __init__(self, data):
self.data = data
# left and right attributes
self.left = None
self.right = None
# creating our nodes
node1 = Node(4)
node2 = Node(2)
node3 = Node(6)
node4 = Node(1)
node5 = Node(3)
node6 = Node(5)
# building our tree
root = node1
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
# search the tree
def search(node, target):
if node is None: # checks if there are no items left to search
return None
elif node.data == target: # checks if the node is our target
return node
elif node.data < target: # go right
return search(node.right, target)
else: # go left
return search(node.left, target)
"""The function will recursively calls itself and check if the value is higher or lower then what we are looking for. For example, we call the function looking for 5. The funcion will figure out that our root node(node1.data == 4) is too small, and therefore go right as a result. Then when it reads our node3.data, it will determine that it is less than 6, and go left as a result. Finally finding 5, and returning the result."""
result = search(root, 5)

# now lets insert a new node into our tree
node7 = Node(7)
def insert(node, new_node):
if new_node.data > node.data:
# put new child on right if space
if node.right is None:
node.right = new_node
return
# otherwise keep looking
else:
insert(node.right, new_node)
if new_node.data < node.data:
# put new child on the left if space
if node.left is None:
node.left = new_node
return
# otherwise keep looking
else:
insert(node.left, new_node)
"""Here we created a Node with the value of 7. This function will recursively call itself until it finds an open spot for 7 -that makes sense in the database. Simularly to our search funtion, it will check -if it cannot find an empty space for our node- if our node's value/data belongs on the left or right side based on how big it is. You can choose any node to try and insert to, but for this example we have used the root node to cycle threw the entire tree."""
insert(root, node7)
insert(root, Node(8))
def delete(node, target):
result = search(node, target - 1)
if result.left == target:
result.left = None
elif result.right == target:
result.right = None
# does a second search to try and find a parent node
result = search(node, target + 1)
if result.left == target:
result.left = None
elif result.right == target:
result.right = None
# else, we print a not found response
else:
print(f"Could not find {target} in Tree.")
"""Here we take advantage of our search function in order to find the previous node. Becuase we are trying to delete 8, we have to look for the node with a value of 7. Note that if we were looking for 5, we would have to look for the parenting node, with a value of 6. As well, this example only works for integer based binary trees."""
delete(root, 8)
# Finally we can print our tree out.
def in_order_traversal(node):
if node is not None:
#traverse
in_order_traversal(node.left)
print(node.data)
in_order_traversal(node.right)
else:
return None
in_order_traversal(root)

And this is what our Tree should look like after it is all said and done. (apologies again for the bad handwriting)

And now a pretty picture to relax your eyes!

Photo by Joel Holland on Unsplash

I know looking at so much text and code can be sore for eyes. Please comment on any questions you might have, and if there’s anything I can do to improve this explanation! But most importantly, happy coding, and have a great day!

--

--

--

I code to create. I code to be challenged. I code for Fun. Software Engineer, New Grad

Recommended from Medium

DIA Partnership with ADD.XYZ

Into Game Mechanics: Guards Eyes— and Touch

That night, Conrad had a pulmonary embolism, which affected his lungs and the right side of the…

Build a scalable Twitter clone with Django and Stream

Promises, Node, Tedious, Azure SQL. Oh My!

Controlling APK Size When Using Native Libraries

How to build a list of who were invited, but not accepted

Egg Catcher!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Anthony S. Protho

Anthony S. Protho

I code to create. I code to be challenged. I code for Fun. Software Engineer, New Grad

More from Medium

Data Structures, Algorithms, And Big O Notation! A Beginners Guide.

Phase 5 of Flatiron School — Project

Linked Lists: An Introduction

Articulation Point!!!!