# Data Structures in Python: Tree

Till now we studied linear data structures in Python. Today, we will look at hierarchical data structure in Python i.e. Trees.

In the above figure, where do you think the root of the tree is? Obviously! to the bottom of the tree. But the tree data structure is upside down which means the root is at the top and leaves are to the bottom of the tree.

Each element of the tree is a node connected via edges. The root node is a level 0 node and the node which has no children/sub-category is a leaf node. In figure level-2 nodes are leaf nodes.

Let’s create a tree node in Python:

`class TreeNode:`

def __init__(self, data):

self.data = data

self.children = []

self.parent = None

Above we created a Tree node where each node has data, children nodes, and a parent node(if it's not a root node)

Now let’s create a method to add a child to TreeNode

class TreeNode:

def __init__(self, data):

self.data = data

self.children = []

self.parent = None def add_child(self, child):

child.parent = self

self.children.append(child)

Now let’s create a method to print tree:

class TreeNode:

def __init__(self, data):

self.data = data

self.children = []

self.parent = None def add_child(self, child):

child.parent = self

self.children.append(child)

def print_tree(self):

print(self.data)

if self.children:

for child in self.children:

self.print_tree()

In the **print_tree **method, we used recursion until children are none.

Now let’s represent the family tree with this TreeNode:

class TreeNode:

def __init__(self, data):

self.data = data

self.children = []

self.parent = None def add_child(self, child):

child.parent = self

self.children.append(child)

def print_tree(self):

print(self.data)

if self.children:

for child in self.children:

self.print_tree()#family tree

def build_family_tree():

grandf = TreeNode("Preethviraj")

f1 = TreeNode("Bhanu")

f2 = TreeNode("Ranu")

grandson1 = TreeNode("Rajesh")

grandson2 = TreeNode("Mahesh")

grandson3 = TreeNode("Raghav") #here root will be grandf and f1,f2 are level 1 & rest leaves

grandf.add_child(f1)

grandf.add_child(f2)

f1.add_child(grandson1)

f1.add_child(grandson2)

f2.add_child(grandson3)

return grandf

Let’s print tree:

class TreeNode:

def __init__(self, data):

self.data = data

self.children = []

self.parent = None def add_child(self, child):

child.parent = self

self.children.append(child)

def print_tree(self):

print(self.data)

if self.children:

for child in self.children:

self.print_tree()#family tree

def build_family_tree():

grandf = TreeNode("Preethviraj")

f1 = TreeNode("Bhanu")

f2 = TreeNode("Ranu")

grandson1 = TreeNode("Rajesh")

grandson2 = TreeNode("Mahesh")

grandson3 = TreeNode("Raghav") #here root will be grandf and f1,f2 are level 1 & rest leaves

grandf.add_child(f1)

grandf.add_child(f2)

f1.add_child(grandson1)

f1.add_child(grandson2)

f2.add_child(grandson3) return grandfif __name__=="__main__":

tree = build_family_tree()

tree.print_tree()

The output will look like this:

`Preethviraj`

Bhanu

Rajesh

Mahesh

Ranu

Raghav

With our output, we can’t determine the level of nodes or which node is the root node and which node is children of which.

To print according to the level of every node we need to know the level of each node that’s why we will add one more method to get the level of each node and then use that method in the print_tree method to print according to levels.

class TreeNode:

def __init__(self, data):

self.data = data

self.children = []

self.parent = None def add_child(self, child):

child.parent = self

self.children.append(child) def get_level(self): #to get level of each node

level =0

p = self.parent

while p:

level += 1

p = p.parent

return level def print_tree(self):

space = ' ' * self.get_level() * 3

prefix = space + '|__' if self.parent else ''

print(prefix + self.data)#add prefix

if self.children:

for child in self.children:

child.print_tree()#family tree

def build_family_tree():

grandf = TreeNode("Preethviraj")

f1 = TreeNode("Bhanu")

f2 = TreeNode("Ranu")

grandson1 = TreeNode("Rajesh")

grandson2 = TreeNode("Mahesh")

grandson3 = TreeNode("Raghav")#here root will be grandf and f1,f2 are level 1 & rest leaves

grandf.add_child(f1)

grandf.add_child(f2)

f1.add_child(grandson1)

f1.add_child(grandson2)

f2.add_child(grandson3)return grandfif __name__=="__main__":

tree = build_family_tree()

tree.print_tree()

Now, our output will be like this:

`Preethviraj`

|__Bhanu

|__Rajesh

|__Mahesh

|__Ranu

|__Raghav

In the above output, we can see properly which node is at which level.

That’s all for today’s tutorial! Bye-bye!

# Lectures

Lecture 1: https://medium.com/@saifmdco/data-structures-with-python-introduction-4dadeffa2215

Lecture 2: https://medium.com/@saifmdco/data-structures-with-python-arrays-c498518bf7fd

Lecture 3: https://medium.com/@saifmdco/data-structures-in-python-lists-653a3ad103ab

Lecture 4: https://medium.com/@saifmdco/data-structures-in-python-tuples-3c350640cd9a

Lecture 5: https://medium.com/@saifmdco/data-structures-in-python-dictionary-fad27ffdda8b

Lecture 6: https://medium.com/@saifmdco/data-structures-in-python-2d-array-6bc0154aa717

Lecture 7: https://medium.com/@saifmdco/data-structures-in-python-matrix-22adba5aa597

Lecture 8: https://medium.com/@saifmdco/data-structures-in-python-sets-92d5445e97e8

Lecture 9: https://medium.com/@saifmdco/data-structures-in-python-chainmap-fca2a9d47249

Lecture 10: https://medium.com/@saifmdco/data-structures-in-python-linkedlist-50f2118c659e

Lecture 11: https://medium.com/@saifmdco/data-structures-in-python-stack-6bf182d63581

Lecture 12: https://medium.com/@saifmdco/data-structures-in-python-queue-6361d3dcff0

Lecture 13: https://medium.com/@saifmdco/data-structures-in-python-dequeue-1a585e269a55

Lecture 14: https://medium.com/@saifmdco/data-structures-in-python-custom-stack-b7b9173b4eae

Lecture 15: https://medium.com/@saifmdco/data-structures-in-python-hash-table-39be784eefc1

Lecture 16: https://medium.com/@saifmdco/data-structures-in-python-doubly-linked-list-fe698d74756c

Lecture 17: https://medium.com/@saifmdco/data-structures-in-python-tree-410255b87107