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.
Representation of 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 grandf
if __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 grandf
if __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