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 11: 2D Arrays - HackerRank 30 days of code solution

Objective Today, we're building on our knowledge of  Arrays  by adding another dimension. Check out the  Tutorial  tab for learning materials and an instructional video! Context Given a    2D Array ,  : 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 We define an hourglass in   to be a subset of values with indices falling in this pattern in  's graphical representation: a b c d e f g There are   hourglasses in  , and an  hourglass sum  is the sum of an hourglass' values. Task Calculate the hourglass sum for every hourglass in  , then print the  maximum  hourglass sum. Input Format There are   lines of input, where each line contains   space-separated integers describing  2D Array   ; every value in   will be in the inclusive range of   to  . Constraints Output Format ...
Read more

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  , ...
Read more

Day 21: Generics - HackerRank 30 days of code solution

Objective Today we're discussing Generics; be aware that  not all languages support this construct , so fewer languages are enabled for this challenge. Task Write a single generic function named  printArray ; this function must take an array of generic elements as a parameter (the exception to this is C++, which takes a  vector ). The locked  Solution  class in your editor tests your function. Note:  You must use generics to solve this challenge.  Do not  write overloaded functions. Input Format The locked  Solution  class in your editor will pass different types of arrays to your  printArray  function. Constraints You must have exactly   function named  printArray . Output Format Your  printArray  function should print each element of its generic array parameter on a new line. Solution : import java.util.*; class Printer <T> {  ...
Read more