HackerRank Day 23 Solution in Python: BST Level Order Traversal

   November 5, 2022

Today we will see the HackerRank Day 23 Solution in Python. The problem is BST Level Order Traversal, part of 30 Days of code on HackerRank. Let’s get started!

Day 23: BST Level Order Traversal Problem statement

We are given a pointer, which points to the root of a binary search tree. Our task is to complete the levelOrder function provided so that it prints the level-order traversal of the binary search tree. A level-order traversal, known as a breadth-first search, visits each level of a tree’s nodes from left to right, top to bottom.

Sample Input

6
3
5
4
7
2
1

Sample Output

3 2 5 1 4 7

Explanation: We traverse each level of the tree from the root downward, and we process the nodes at each level from left to right. The resulting level-order traversal is 3->2->5->1->4->7, and we print these data values as a single line of space-separated integers.

You can solve the problem here.

HackerRank Day 23 Solution in Python

import sys

class Node:
    def __init__(self,data):
        self.right=self.left=None
        self.data = data
        
class Solution:
    def insert(self,root,data):
        if root==None:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left,data)
                root.left=cur
            else:
                cur=self.insert(root.right,data)
                root.right=cur
        return root

    #Function to perform Level order traversal
    def levelOrder(self,root):
        #Create list to store the iterations and result
        current_level = [root]
        next_level = []
        result = []
        
        #Iterate through the tree
        while current_level:
            next_level = []
            
            #Iterate through the level
            for node in current_level:
                result.append(str(node.data))
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            
            #Increment to the next level
            current_level = next_level
        
        #Print the result of level order traversal
        print(" ".join(result))
        
T=int(input())
myTree=Solution()
root=None
for i in range(T):
    data=int(input())
    root=myTree.insert(root,data)
myTree.levelOrder(root)

Code Explanation

  • First, we create a levelOrder function to perform Level order traversal
  • Create a list current_level to start with the root, next_level to store the subsequent iterations, and result to keep the level order traversal output
  • Iterate through the tree through each level. Add the node data to the result if present, then check for the left and right nodes and add them to the list
  • Increment the current level to the next level and repeat the steps
  • Finally, we print the result list
Best 100+ Python Projects with source code

Also Read:

Share:

Author: Ayush Purawr