package tree;
public class Node{
private Node left;
private Node right;
private int data;
public Node(int data){
this.data=data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
package tree;
import java.util.LinkedList;
import java.util.Queue;
public class AddNodeInBinaryTree {
private Node rootNode;
public static void main(String[] args) {
new AddNodeInBinaryTree();
}
public AddNodeInBinaryTree(){
addNode(rootNode, 1);
addNode(rootNode, 2);
addNode(rootNode, 3);
addNode(rootNode, 4);
addNode(rootNode, 5);
printTreeLevelOrder(rootNode);
}
private void printTreeLevelOrder(Node rootNode){
if(rootNode==null)
return;
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()){
Node obj = (Node)queue.poll();
System.out.print(obj.getData() + " ");
if(obj.getLeft()!=null)
queue.add(obj.getLeft());
if(obj.getRight()!=null)
queue.add(obj.getRight());
}
}
private void addNode(Node rootNode, int data){
//First check is there any Nodes present.
if(rootNode==null){
// No Nodes are Present, create one and assign it to startNode
Node temp1=new Node(data);
this.rootNode=temp1;
}else{
//Nodes present, So check the proper position where to add New Node.
//Checking whether Left child and Right child are present for root Node.
if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
//Left and Right Child exist, Also, we need to add ne Node in Sequential Fashion of Left and Right,
//We have to scan all Levels one by one to check a proper place for new Node.
//Also, we for each and every node we need to check whether Left and Right Exist,
//So we need to store them for later Processing that is why we introduced Queue.
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()){
Node obj = (Node)queue.poll();
if(obj.getLeft()!=null && obj.getRight()!=null){
queue.add(obj.getLeft());
queue.add(obj.getRight());
}else if(obj.getLeft()==null){
Node temp1=new Node(data);
obj.setLeft(temp1);
break;
}else{
Node temp1=new Node(data);
obj.setRight(temp1);
break;
}
}
}else{
// We reach this condition when either Left or Right is Null, but not sure which side is Null.
if(rootNode.getLeft()==null){
Node temp1=new Node(data);
rootNode.setLeft(temp1);
}else{
Node temp1=new Node(data);
rootNode.setRight(temp1);
}
}
}
}
}
No comments:
Post a Comment