How to do Level order traversal in Binary Search Tree

How to do Level order traversal in Binary Search Tree

Level order traversal  

We have see lot of tutorials based on Binary tree and also other traversals like Inorder, Preorder and Postorder etc.,

Now in this tutorial lets see how to do Level order traversal of Binary Search Tree using Queue. From the given below tree we need to get output as F, D, J, B, E, G, K, A, C I, H

Solution:

• Place the root node in Queue.
• Iterate Queue until queue becomes empty. Dequeue the first node from Queue and print the value of that node.
• Next Enqueue the child nodes left and right nodes inside same queue. 
• Repeat the process until each leaf node. 

Here in above example first we need to place 'F' node inside queue. Next in loop we need to print 'F' and get the child nodes 'D' and 'J' and enqueue inside same queue. Repeat the process until all leaf nodes and when Queue becomes empty.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class LevelOrderTraversal {
 
 public static void main(String[] args) {

  int a[] = { 11, 6, 19, 4, 8, 5, 43, 49, 10, 31, 17, 5 };

  Node root = null;
  LevelOrderTraversal tree = new LevelOrderTraversal();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }
  tree.levelOrderTraversal(root);
 }

 public void levelOrderTraversal(Node root) {

  if (root == null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  System.out.println(root.data);

  while (queue.size() > 0) {
   Node current = queue.poll();
   if (current.left != null) {
    System.out.println(current.left.data);
    queue.add(current.left);
   }
   if (current.right != null) {
    System.out.println(current.right.data);
    queue.add(current.right);
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

11
6
19
4
8
17
43
5
10
31
49

Inorder Predecessor and Successor of Binary Search Tree

Inorder Predecessor and Successor of Binary Search Tree

Successor  

In a given Binary Search Tree need to find the predecessor and Successor of a given node.

What is Predecessor and Successor ?

In a given Binary Search Tree highest element on the left subtree is the Predecessor and lowest element on the right subtree is the Successor of the given node. For example in a below given binary search tree if we need to find Predecessor and Successor of node 28

then, node 20 will be the Predecessor and node 36 will be the Successor.

Lets see simple example as how to find Inorder Predecessor and Successor for any given binary tree.

public class PredecessorSuccessor {

 class BST {

  BST left; // Left subtree
  BST right; // Right subtree
  int data; // Element

  public BST(int data) {
   this.data = data;
  }
 }

 private int predecessor = -1;
 private int successor = -1;
 private int previous = -1;

 public static void main(String[] args) {

  int val[] = new int[] { 28, 15, 40, 19, 10, 36, 45, 20, 5, 50 };

  int findPreSuc = 28;
  
  PredecessorSuccessor obj = new PredecessorSuccessor();

  BST root = obj.createBST(val);

  obj.getPredecessorSuccessor(root, findPreSuc);
  
  System.out.println("Given node element : "+findPreSuc);
  
  if(obj.predecessor == -1) {
   System.out.println("No Predecessor for the given node ");
  }else {
   System.out.println("Predecessor : " + obj.predecessor);

  }if(obj.successor == -1) {
   System.out.println("No Successor for the given node ");
  }else {
   System.out.println("Successor : " + obj.successor);

  }
 }

 // BST in-order traversal
 public void getPredecessorSuccessor(BST root, int findPreSuc) {

  // Return once we got both Predecessor and Successor
  if (predecessor != -1 && successor != -1) {
   return;
  }

  // Recursive to left subtree
  if (root.left != null) {
   getPredecessorSuccessor(root.left, findPreSuc);
  }

  // Getting Predecessor
  if (root.data == findPreSuc) {
   predecessor = previous;
  }

  // Getting Successor
  if (findPreSuc == previous) {
   successor = root.data;
   previous = root.data;
   return;
  }
  previous = root.data;
  
  // Recursive to right subtree
  if (root.right != null) {
   getPredecessorSuccessor(root.right, findPreSuc);
  }

 }

 public BST createBST(int[] val) {

  BST root = new BST(val[0]); // Root node with 1st element
  BST tmpRoot = root;

  for (int i = 1; i < val.length; i++) {

   BST lastNode = getLastNode(tmpRoot, val[i]);

   if (val[i] > lastNode.data) {

    BST tmp = new BST(val[i]);
    lastNode.right = tmp;

   } else {

    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }

  return root;
 }

 public BST getLastNode(BST root, int val) {

  if (val > root.data) {

   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {

   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }
}

OUTPUT:

Given node element : 28
Predecessor : 20
Successor : 36

Know How to find all leaf nodes in binary tree

Know How to find all leaf nodes in binary tree

Print all leaf nodes of a Binary Tree from left to right  

Create a Binary Tree with from the given array of values and then find all the leaf nodes from left to right. Leaf nodes are nothing but bottom/last nodes with both left and right subtree's are null.
For the below given Binary tree the list of leaf nodes will be 1, 6, 9

Lets see simple java code to create a binary with the given array of integers and to find the leaf nodes.

public class BinaryTreeLeafNode {

 public static void main(String[] args) {

  int val[] = new int[] { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };
  
  BinaryTree obj = new BinaryTree();

  BST root = obj.createBinaryTree(val);

  obj.getAllLeafNodes(root);
 }

 public BST createBinaryTree(int[] val) {
  BST root = new BST(val[0]); // Initialize root with 1ft element
  BST tmpRoot = root; // Temporary root node

  for (int i = 1; i < val.length; i++) {

   BST lastNode = getLastNode(tmpRoot, val[i]);
   if (val[i] > lastNode.data) {
    BST tmp = new BST(val[i]);
    lastNode.right = tmp;
   } else {
    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }
  return root;
 }

 public void getAllLeafNodes(BST root) {
  if (root.left != null) {
   getAllLeafNodes(root.left);
  }
  if (root.right != null) {
   getAllLeafNodes(root.right);
  }
  /*
   * If both left and right are null then its leaf node
   */
  if(root.left == null && root.right == null) {
   System.out.print(root.data + ", ");
  }
 }

 public BST getLastNode(BST root, int val) {

  if (val > root.data) {
   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {
   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }
}

OUTPUT:

1, 6, 9, 

Simple, how to get only left child in BST

Simple, how to get only left child in BST

Simple  

As same as traversals like inorder, preorder, postorder and level order we need to traverse to BST and need to print only the left child of each nodes in Binary Search Tree.
From below example we need to get only the nodes including root nodlike 11, 6, 4, 17, 31

Solution:

• Place the root node in Queue.
• Iterate Queue until queue becomes empty. 
• Next Enqueue the child nodes left and right nodes inside same queue and print only the left node values. 
• Repeat the process for each leaf node.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class LeftNodes {

 public static void main(String[] args) {

  int a[] = { 4, 5, 3, 8, 7, 6, 100, 9, 3, 2, 1 };

  Node root = null;
  LeftNodes tree = new LeftNodes();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }
  tree.printLeftNodes(root);
 }

 public void printLeftNodes(Node root) {

  if (root == null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  System.out.println(root.data);

  while (queue.size() > 0) {
   Node current = queue.poll();
   if (current.left != null) {
    System.out.println(current.left.data);
    queue.add(current.left);
   }
   if (current.right != null) {
    queue.add(current.right);
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

4
3
2
1
7
6
9

Sorting Integer array without any sorting algorithm or loop ?

Sorting Integer array without any sorting algorithm or loop ?

Sorting Integer array without any sorting algorithm or loop  

In this tutorial we will see about how to sort and print the integer array without using any sorting algorithm or without using any loop to sort. Here it comes the Data Structure and we are going to use Binary Search Tree with In-order traversal. Just need to create BST with the given array and traverse through BST using In-order traversal. By this way we can sort given array without using any sorting algorithm or loop to sort the given array.

Lets see simple Java code how to create BST with the given integer array and to traverse through BST and print the given array in sorted order.

class BST {

 BST left; // Left subtree
 BST right; // Right subtree
 int data; // Element

 public BST(int data) {
  this.data = data;
 }
}


public class SortingWithoutLoop {

 public static void main(String[] args) {

  int val[] = new int[] { 5, 8, 3, 7, 0, 43, 65, 8, 2, 89, 25 };
  BST root = new BST(val[0]);
  for (int i = 1; i < val.length; i++) {
   BST lastNode = getLastNode(root, val[i]);
   if (val[i] > lastNode.data) {
    BST tmp = new BST(val[i]);
    lastNode.right = tmp;
   } else {
    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }
  
  inOrderTraversal(root);
 }

 public static BST getLastNode(BST root, int val) {

  if (root.right != null && val > root.data) {
   return getLastNode(root.right, val);
  } else if(root.left != null && val < root.data){
   return getLastNode(root.left, val);
  }
  return root;
 }

 public static void inOrderTraversal(BST root) {

  if (root.left != null) {
   inOrderTraversal(root.left);
  }

  System.out.print(root.data + ", ");

  if (root.right != null) {
   inOrderTraversal(root.right);
  }
 }
}

OUTPUT:

0, 2, 3, 5, 8, 8, 25, 43, 65, 89,