Day 23: BST Level-Order Traversal HackerRank Solution

Day 23: BST Level-Order Traversal HackerRank Solution
Source : https://www.hackerrank.com/challenges/30-binary-trees

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.

Source : https://www.hackerrank.com/challenges/30-binary-trees

Solution

	// Karthikalapati.blogspot.com
	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) {
	if (root == null) {
	return;
	}
	ArrayDeque<Node> deque = new ArrayDeque(); // use deque as a queue
	deque.add(root);
	while (!deque.isEmpty()) {
	Node n = deque.removeFirst();
	System.out.print(n.data + " ");
	if (n.left != null) {
	deque.addLast(n.left);
	}
	if (n.right != null) {
	deque.addLast(n.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);
	}
	}