Binary Tree Vertical Order Traversal

In this class, We discuss Binary Tree Vertical Order Traversal.

Readers can prepare a full competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given a binary tree.

Our task is to display keys in vertical order from left to right.

The below diagram shows the vertical order traversal example.

In the above diagram, Nodes 6 and 5 are on the same horizontal and vertical levels.

If nodes are on the same horizontal level, we must maintain level order traversal display.

Time complexity: O(N)

Space complexity: O(N)

Logic:

The level order traversal of the tree is done using a queue data structure.

During the level order traversal, we need to maintain the vertical order.

How do we maintain the vertical order?

Using an extra variable, we maintain the vertical order traversal.

When we move to the node’s left, we reduce the variable by 1.

When we move the right of the node, we increase the variable by 1.

To maintain the vertical order, we use a hash table.

The explanation is provided step-by-step in the video.

Code:

class Node:

    # Constructor to create a new node

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

class Solution:

    def verticalTraversal(self, root):

        m = dict()

        hd = 0

        que=[]

        que.append([root,hd])

        while(len(que)!=0):

            z=que.pop(0)

            if(z[0].left!=None):

                que.append([z[0].left,z[1]-1])

            if(z[0].right!=None):

                que.append([z[0].right,z[1]+1])

            try:

                m[z[1]].append(z[0].val)

            except:

                m[z[1]] = [z[0].val]

        k=[]

        for index, value in enumerate(sorted(m)):

            k.append(m[value])

        return k

if __name__ == ‘__main__’:

    root = Node(1)

    root.left = Node(2)

    root.right = Node(3)

    root.left.left = Node(4)

    root.left.right = Node(5)

    root.right.left = Node(6)

    root.right.right = Node(7)

    root.right.left.right = Node(8)

    root.right.right.right = Node(9)

    print(“Vertical order traversal is”)

    ob=Solution()

    z=ob.verticalTraversal(root)

    print(z)