# 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: 
-1: [7, 6]
0: [10, 8, 14]
1: [16, 15, 17]
2: 
3: ```

Hope. you liked the post.