Java Day 23: BST Level-Order Traversal



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, root , 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.



  1. import java.io.*;
  2. import java.util.*;
  3. class Node{
  4. Node left,right;
  5. int data;
  6. Node(int data){
  7. this.data=data;
  8. left=right=null;
  9. }
  10. }
  11. class Solution{
  12. public static void levelOrder(Node root) {
  13. Queue<Node> queue = new LinkedList<>();
  14. queue.add(root);
  15. while (!queue.isEmpty()) {
  16. Node curr = queue.remove();
  17. System.out.print(curr.data + " ");
  18. if (curr.left != null) queue.add(curr.left);
  19. if (curr.right != null) queue.add(curr.right);
  20. }
  21. }
  22. public static Node insert(Node root,int data){
  23. if(root==null){
  24. return new Node(data);
  25. }
  26. else{
  27. Node cur;
  28. if(data<=root.data){
  29. cur=insert(root.left,data);
  30. root.left=cur;
  31. }
  32. else{
  33. cur=insert(root.right,data);
  34. root.right=cur;
  35. }
  36. return root;
  37. }
  38. }
  39. public static void main(String args[]){
  40. Scanner sc=new Scanner(System.in);
  41. int T=sc.nextInt();
  42. Node root=null;
  43. while(T-->0){
  44. int data=sc.nextInt();
  45. root=insert(root,data);
  46. }
  47. levelOrder(root);
  48. }
  49. }