Day 23: BST Level-Order Traversal - HackerRank 30 days of code solution

Objective
Today, we're going further with Binary Search Trees. Check out the Tutorial tab for learning materials and an instructional video!
Task
A level-order traversal, also known as a breadth-first search, visits each level of a tree's nodes from left to right, top to bottom. You are given a pointer, , pointing to the root of a binary search tree. Complete the levelOrder function provided in your editor so that it prints the level-order traversal of the binary search tree.
Hint: You'll find a queue helpful in completing this challenge.
Input Format
The locked stub code in your editor reads the following inputs and assembles them into a BST:
The first line contains an integer,  (the number of test cases).
The  subsequent lines each contain an integer, , denoting the value of an element that must be added to the BST.
Output Format
Print the  value of each node in the tree's level-order traversal as a single line of  space-separated integers.
Sample Input
6
3
5
4
7
2
1
Sample Output
3 2 5 1 4 7
Explanation
The input forms the following binary search tree:
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 , and we print these data values as a single line of space-separated integers.

Solution :

import java.io.*;
import java.util.*;
class Node{
    Node left,right;
    int data;
    Node(int data){
        this.data=data;
        left=right=null;
    }
}
class Solution{
static void levelOrder(Node root){
      //Write your code here
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node curr = queue.remove();
            System.out.print(curr.data + " ");

            if (curr.left != null) queue.add(curr.left);
            if (curr.right != null) queue.add(curr.right);
        }
      
    }
public static Node insert(Node root,int data){
        if(root==null){
            return new Node(data);
        }
        else{
            Node cur;
            if(data<=root.data){
                cur=insert(root.left,data);
                root.left=cur;
            }
            else{
                cur=insert(root.right,data);
                root.right=cur;
            }
            return root;
        }
    }
    public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            int T=sc.nextInt();
            Node root=null;
            while(T-->0){
                int data=sc.nextInt();
                root=insert(root,data);
            }
            levelOrder(root);
        }
}

Comments

Post a Comment

Popular posts from this blog

Day 4: Class vs. Instance - HackerRank 30 days of code solution

Objective In this challenge, we're going to learn about the difference between a  class  and an  instance ; because this is an  Object Oriented concept, it's only enabled in certain languages. Check out the  Tutorial  tab for learning materials and an instructional video! Task Write a  Person  class with an instance variable,  , and a constructor that takes an integer,  , as a parameter. The constructor must assign   to   after confirming the argument passed as   is not negative; if a negative argument is passed as  , the constructor should set   to   and print  Age is not valid, setting age to 0. . In addition, you must write the following instance methods: yearPasses()  should increase the   instance variable by  . amIOld()  should perform the following conditional actions: If  , print  You are young. . If   and  , print  You are a teenager. . Otherwise, print  You are old. . To help you learn by example and complete this challenge, much of the code is provi
Read more

Day 12: Inheritance - HackerRank 30 days of code solution

Image
Objective Today, we're delving into Inheritance. Task You are given two classes,  Person  and  Student , where  Person  is the base class and  Student  is the derived class. Completed code for  Person  and a declaration for  Student  are provided for you in the editor. Observe that  Student  inherits all the properties of  Person . Complete the  Student  class by writing the following: A  Student  class constructor, which has   parameters: A string,  . A string,  . An integer,  . An integer array (or vector) of test scores,  . A  char calculate()  method that calculates a Student object's average and returns the grade character representative of their calculated average: Input Format The locked stub code in your editor calls your  Student  class constructor and passes it the necessary arguments. It also calls the  calculate  method (which takes no arguments). You are not responsible for reading the following input from stdin: The first line
Read more

Day 27: Testing - HackerRank 30 days of code solution

This problem is all about unit testing. Your company needs a function that meets the following requirements: For a given array of   integers, the function returns the index of the element with the minimum value in the array. If there is more than one element with the minimum value, the returned index should be the smallest one. If an empty array is passed to the function, it should raise an Exception. Note: The arrays are indexed from  . A colleague has written that function, and your task is to design   separated unit tests, testing if the function behaves correctly. The implementation in Python is listed below (Implementations in other languages can be found in the code template): def minimum_index ( seq ): if len ( seq ) == 0 : raise ValueError ( "Cannot get the minimum value index from an empty sequence" ) min_idx = 0 for i in range ( 1 , len ( seq )): if a [ i ] < a [ min_idx ]: min_idx = i
Read more