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

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

Counting nodes in a tree? Yes how to get Binary Tree size

Counting nodes in a tree? Yes how to get Binary Tree size

Data Structure  

Counting nodes in a tree? Yes how to get Binary Tree size nothing but counting all the nodes in a Binary Tree. For example the size of the below binary tree is 11

Lets see simple Java code to create Binary Tree and to find the size of the tree as well.

class Node {
 Node left, right;
 int data;

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

public class BinaryTreeSize {

 public static void main(String[] args)  {

  int a[] = { 11, 6, 19, 4, 8, 17, 43, 5, 10, 31, 49 };
  Node root = null;
  BinaryTreeSize tree = new BinaryTreeSize();

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

  int count = tree.binaryTreeSize(root);
  System.out.println("Binary Tree size : " + count);
 }

 public int binaryTreeSize(Node root) {
  return nodeCount(root, 0);
 }

 /*
  * Getting binary tree size using recursive algorithm
  */
 public int nodeCount(Node root, int val) {
  if (root != null) {
   val++;
   val = nodeCount(root.left, val);
   val = nodeCount(root.right, val);
  }
  return val;
 }

 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:

Binary Tree size : 11

How to do Iterative Postorder Traversal in BST

How to do Iterative Postorder Traversal in BST

Postorder  

Earlier we have seen lot of tutorials related to Binary Search Tree like

How to find the diameter of a binary tree
Converting a Binary Tree into its Mirror Tree
Inorder Predecessor and Successor of Binary Search Tree
How to find all leaf nodes in Binary Search Tree

In this tutorial we will see how to do postorder traversal using iterative method instead of recrusive algorithm. We are going to use single stack to store nodes and applying our logic over it to get postorder traversal.

Simple Java code to create Binary Search Tree and doing postorder traversal using iterative method.

import java.util.Stack;

class Node {
 Node left, right;
 int data;

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

public class PostOrderTraversal {

 public static void main(String[] args)  {

  int a[] = { 4, 5, 8, 100, 3, 2, 9, 1, 7, 6 };
  Node root = null;
  PostOrderTraversal tree = new PostOrderTraversal();

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

  System.out.println("\n\nBy Stack : ");
  tree.postOrderTraversal(root);

 }

 /*
  * Postorder traversal using iteration and single stack
  */
 public void postOrderTraversal(Node root)  {

  //Stack to store each node
  Stack<Node> stack = new Stack<Node>();

  //Strong all left node from root into stack
  while (root != null) {
   stack.push(root);
   root = root.left;
  }
  Node node = null;

  while (stack.size() > 0) {

   // Boolean flag to check left and right nodes are visited or not
   boolean leftVisited = false, rightVisited = false;

   // Checking whether current node is equal to roots left node (1)
   if (node != null && stack.peek().left == node) {
    leftVisited = true;

   // Checking whether current node is equal to roots right node (2)
   } else if (node != null && stack.peek().right == node) {
    leftVisited = rightVisited = true;

   }
   node = stack.peek();

   // if above check (1) fails then push current nodes left node into stack
   if (node.left != null && !leftVisited) {
    stack.push(node.left);
   // if above check (2) fails then push current nodes right node into stack
   } else if (node.right != null && !rightVisited) {
    stack.push(node.right);

   } else {
    node = stack.pop();
    System.out.print(node.data + ", ");
   }
  }
 }

 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:

By Stack : 
1, 2, 3, 6, 7, 9, 100, 8, 5, 4, 

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