# Linked lists & Binary Trees

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 = Nonenode1 = 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 regardlessself.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).

The circles represent our nodes, that are holding ** ints** as data. The

**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.next***is added, as to go the other direction in our Double Linked List. Just as the tail points to**

*node.previous**None*, so will our

**when at the beginning of the list.**

*node.previous*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

**attribute. However, there is a**

*.previous***and .**

*.left***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.**

*right*#!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 Nonein_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!

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!