Vertical Order Traversal of Binary Tree in Python
By Om AvhadHello everyone, let’s learn how to traverse a Binary Tree in Vertical Order Traversal with Python.
Binary Trees are traversed using various different types of traversal methods like pre-order traversal, inorder traversal, post-order traversal, etc.
Every node is at some distance from the parent and root of the Binary Tree. Let’s assign an ‘x’ co-ordinate to every node of the Binary Tree.
We’ll consider the root node as the origin and each left child will have the ‘x’ co-ordinate 1 less than their parent node. Similarly, the right child will have the ‘x’ coordinate 1 more than their parent node.
Firstly, let’s create a ‘TreeNode’ class which will be containing all the required functions such as insert, traverse. Each node will be having 4 variables which will store the data, the ‘x’ coordinate, the left node and the right node.
While traversing we’ll keep adding the ‘x’ coordinate to a dictionary. The keys can be then sorted and the respective value can be printed.
Python code for Vertical Order Traversal of Binary Tree
Below is the given code in Python to perform our task:
class Node(object):
def __init__(self, data, x= 0):
self.value = data
self.left = None
self.right = None
self.x_coord = x
def insert(self, data):
if (data <= self.value):
if (self.left == None):
self.left = Node(data, x= (self.x_coord - 1))
else:
self.left.insert(data)
elif (data > self.value):
if (self.right == None):
self.right = Node(data, x= (self.x_coord + 1))
else:
self.right.insert(data)
class VerticalTraverse(object):
def __init__(self):
self.data = dict()
def traverse(self, root):
self._traverse(root)
keys = sorted(self.data.keys())
for key in keys:
print("{}: {}".format(key, self.data[key]))
def _traverse(self, node):
x = node.x_coord
if x in self.data.keys():
self.data[x].append(node.value)
else:
self.data[x] = [node.value]
if node.left is not None:
self._traverse(node.left)
if node.right is not None:
self._traverse(node.right)
def main():
root = Node(10)
arr = [7, 4, 6, 16, 14, 8, 18, 19, 17, 15]
for ele in arr:
root.insert(ele)
obj = VerticalTraverse()
obj.traverse(root)
main()
The output of the above code is:
$ python main.py -2: [4] -1: [7, 6] 0: [10, 8, 14] 1: [16, 15, 17] 2: [18] 3: [19]
Hope. you liked the post.
Read more:
- How to implement a Binary Tree in Python
- Python program to find the parent of a node in a Binary
- Python program for converting a given binary tree to a doubly linked list
Amazing! Really insightful. I have tried in C++ but was facing errors in python, this post really solved my doubts.