# Vertical Order Traversal of Binary Tree in Python

Hello 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:

## Leave a Reply

You must be logged in to post a comment.