KKR
BAN USERBuilding Binary search tree is a good approach...
The only thing is creating the binary search tree will take O(n.logn) time...which is better option as compared to sorting and then searching.....
But i still think hasmap implementation is a good approach large number of elements, given we can use extra memory to maintain hashmap in memory..
but for 20 elements if we have a constraint of memory sorting will be the best option elements..which will take O(20 log 20) for sorting and traversing 20 elements in worst case to check the neighboring elements in an array..
Please comment if you guys disagree!!!
public static void printTheLevelAtWhichTheBinaryTreeIsComplete(TreeNode node) {
if (node == null) {
System.out.println("The tree is empty.");
System.out.println("-1");
}
int level = 0;
TreeNode delimeter = new TreeNode(-1);
TreeNode temp = null;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(node);
q.add(delimeter);
while (!q.isEmpty()) {
temp = q.remove();
if (temp == delimeter) {
level += 1;
q.add(delimeter);
continue;
}
if (temp.left != null && temp.right != null) {
if (temp.left != null)
q.add(temp.left);
if(temp.right != null)
q.add(temp.right);
} else {
break;
}
}
System.out.println("At level " + level + " the Tree is balanced.");
}
It is the working code.. Please check..:)
- KKR July 31, 2012Please comment on the above code if you have any doubt..and also find the whole linked program for the same...
package linkedlists;
public class LinkedList {
Node HEAD;
public Node getHEAD() {
return HEAD;
}
public void setHEAD(Node hEAD) {
HEAD = hEAD;
}
public Node getTAIL() {
return TAIL;
}
public void setTAIL(Node tAIL) {
TAIL = tAIL;
}
Node TAIL;
public LinkedList(Node HEAD,Node TAIL) {
this.HEAD = HEAD;
this.TAIL = TAIL;
}
public void traveseList(){
Node n = this.HEAD;
while(n != null){
System.out.println("Value at Node::" + n.getKey());
n = n.getNext();
}
}
public void reverseList(){
Node n,n1,n2;
n = this.HEAD;
n1 = n.getNext();
n2 = n1.getNext();
this.TAIL = n;
n.setNext(null);
while(n1.getNext() != null){
n1.setNext(n);
n = n1;
n1 = n2;
n2 = n2.getNext();
}
n1.setNext(n);
this.HEAD = n1;
}
public void replaceKthCharacter(int k){
Node kthElementFromStart,slow , fast;
slow = fast = this.getHEAD();
if(slow == null || fast == null){
System.out.println("List is empty..");
return;
}
int i;
for( i = 1; i< k; i++){
fast = fast.getNext();
if(fast == null){
System.out.println("List is of size:: " + i + " which is lesser then::" + k);
return;
}
}
kthElementFromStart = fast ;
while(fast != null && fast.getNext() != null){
fast = fast.getNext();
slow = slow.getNext();
}
String tmpKey = kthElementFromStart.getKey();
kthElementFromStart.setKey(slow.getKey());
slow.setKey(tmpKey);
this.traveseList();
}
public static void main(String[] args) {
Node n1 = new Node();
Node n2 = new Node();
Node n3 = new Node();
Node n4 = new Node();
Node n5 = new Node();
Node n6 = new Node();
n1.setKey("JAVA");
n2.setKey("RUBY");
n3.setKey("HTML");
n4.setKey("C++");
n5.setKey("C");
n6.setKey("Obj C");
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(null);
LinkedList list = new LinkedList(n1, n6);
list.traveseList();
list.reverseList();
System.out.println("Revers List...");
list.traveseList();
list.replaceKthCharacter(3);
}
}
//Create a class Node
public class Node {
String key;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
Node next ;
}
//Create a Singly Linked List
public class LinkedList {
Node HEAD;
Node TAIL;
public LinkedList(Node HEAD,Node TAIL) {
this.HEAD = HEAD;
this.TAIL = TAIL;
}
public void traveseList(){
Node n = this.HEAD;
while(n != null){
System.out.println("Value at Node::" + n.getKey());
n = n.getNext();
}
}
public void reverseList(){
Node n,n1,n2;
n = this.HEAD;
n1 = n.getNext();
n2 = n1.getNext();
this.TAIL = n;
n.setNext(null);
while(n1.getNext() != null){
n1.setNext(n);
n = n1;
n1 = n2;
n2 = n2.getNext();
}
n1.setNext(n);
this.HEAD = n1;
}
public static void main(String[] args) {
Node n1 = new Node();
Node n2 = new Node();
Node n3 = new Node();
Node n4 = new Node();
Node n5 = new Node();
Node n6 = new Node();
n1.setKey("JAVA");
n2.setKey("RUBY");
n3.setKey("HTML");
n4.setKey("C++");
n5.setKey("C");
n6.setKey("Obj C");
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(null);
LinkedList list = new LinkedList(n1, n6);
list.traveseList();
list.reverseList(); // Reverse the list
System.out.println("Revers List...");
list.traveseList();
}
}
Hi please find the java code to convert the input array into a linkedlist each node containing a sequence.
Please reply if you find any mistakes .
- KKR November 22, 2012