Vertical Order Traversal of Binary Tree in Python

By Om Avhad

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