Bottom View of a Binary Tree

In this class, We discuss the Bottom View of a Binary Tree.

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 print the elements of the bottom view of the binary tree.

A node is included in the bottom view if seen from the Bottom of the binary tree.

The below diagram shows the bottom view example.

If more than one node is present at the same level, we need to display the last node in level order traversal

Time complexity: O(N)

Space complexity: O(N)

Logic:

We do the same as vertical order traversal.

In vertical order traversal, we maintained all the nodes in the vertical order.

Here we maintain the last node in the vertical order traversal.

The last node in each vertical order is the node in the bottom view.

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 bottomView(self, root):

        # code here

        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])

            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(“Bottom View”)

    ob=Solution()

    z=ob.bottomView(root)

    print(z)