Trees | A beautiful data structure

During my journey from the forest of data structures I saw a tree and I loved it :D Pardon me for the casual joke.
But yes, today I would like to talk a bit about Tree data structure.

If you have ever used a social media platform - you have been exposed to a system which heavily used trees data structure. Some people classify it as a hard one to understand but I think it is fascinating and makes our lives easier in a lot of cases.

The tutorial timeline will look something like this:

• What is Tree?
• Why it exist?
• Types of Tree?
• Real world examples
• Implementation

Tree - What is it?

It is a non-linear hierarchal data structure that consists of nodes and edges. So it is a lot of new words so first let's get out the new terms out of the way.

• Non-linear hierarchal: Unlike arrays or linked list this data structure is designed to hold data which is linked in a hierarchal manner. Hierarchal means it is capable of holding data which has a parent child relation within.
• Node: A node is an entity that contains a key or value and pointers to its child nodes.
• Edge: The link between any two nodes is called an edge.

NOTE: Tree is a data structure, and binary tree is a type of this data structure. Every binary tree is a tree but every tree is not a binary tree.

Tree - Why?

In simple words, we needed something to access data in an efficient way. Tree access time is better than linked list.

Another reason: Trees are really useful when you want to save data which naturally forms a hierarchal relation. Simplest common world example can be a family tree and rather trivial tech example can be one database indexing.

Real world examples

• Database indexing is used using a special kind of tree called B-Tree or B+ Tree.
• DNS - It also uses a tree data structure.
• In some machine learning algorithm decision tree based learning is used.
• XML parsers use trees.
• Binary search tree, Heaps, Heap Sort, Huffman coding tree, syntax tree are also some of the examples where trees are used.

Implementation

Enough verbose, let get straight into the implementation.
As we know, tree is a collection to nodes related to each other with the edges so what does a tree node look like?

class Node():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Let's say if we want to create a tree like below. How can we do that?

#     1
#    / \
#   2   3
#  / \
# 4   5

One way would be to do it manually creating root/parent nodes and adding children to it but I would like to share a better way. We can write a function which recursively creates a tree from array.

nodes = [1,2,3,4,5]

The above array is the representation of the tree we are talking about and if you notice, if i is the parent node the left child is 2i+1 and the right child is 2i+2. Using this we can easily write the function to create the tree.

nodes = [1,2,3,4,5]

def createTree(nodes, i):
    if i >= len(nodes):
        return None

    root = Node(nodes[i])
    root.left = createTree(nodes, 2 * i + 1)
    root.right = createTree(nodes, 2 * i + 2)
    return root

Hmm, now we have created our tree but how can we see it? or more formally speaking, how can we visit all the nodes of our tree?
This is called traversing. If English is not your first language, like me, traversing means "travel across or through." or simply "move back and forth or sideways".
So how can we do that?
Traversing is mainly three types and it depends on the root node.

• Pre-order
• Post-order
• In-order

Photo by Rodrigo Santos