Binary Tree Connected

Binary Tree Connected
1. Node.java

 package com.nrs.ds.tree.ex;  
 public class Node {  
      String data;  
      Node left, right, nextRight;  
      Node(String string){  
           data = string;  
           left=right=nextRight=null;  
      }  
 }
2.BinaryTreeConnected.java

 package com.nrs.ds.tree.ex;  
 public class BinaryTreeConnected {  
      Node root;  
      void connect(Node p){  
           p.nextRight = null;  
           connectRecur(p);  
      }  
      void connectRecur(Node p){  
           if(p == null){  
                return;  
           }  
           if(p.left != null){  
                p.left.nextRight = p.right;  
           }  
           if(p.right != null){  
                p.right.nextRight = (p.nextRight != null) ? p.nextRight.left:null;  
           }  
           connectRecur(p.left);  
           connectRecur(p.right);  
      }  
 }
3. Test 
 package com.nrs.ds.tree.ex;  
 public class BinaryTreeConnectTest {  
      public static void main(String[] args) {  
           BinaryTreeConnected btc = new BinaryTreeConnected();  
           btc.root = new Node("A");  
           btc.root.left = new Node("B");  
           btc.root.right = new Node("C");  
           btc.root.left.left = new Node("D");  
           btc.root.left.right = new Node("E");  
           btc.connect(btc.root);  
            System.out.println("Following are populated nextRight pointers in the tree (-1 is printed if there is no neextRight)");  
            String a = btc.root.nextRight != null ? btc.root.nextRight.data : "NULL";  
            System.out.println("nextRight of "+ btc.root.data +"is "+a);  
            String b = btc.root.left.nextRight != null ? btc.root.left.nextRight.data : "NULL";  
            System.out.println("nextRight of "+ btc.root.left.data +"is "+b);  
            String c = btc.root.right.nextRight != null ? btc.root.right.nextRight.data :"NULL";  
            System.out.println("nextRight of "+ btc.root.right.data +"is "+c);  
            String d = btc.root.left.left.nextRight != null ? btc.root.left.left.nextRight.data : "NULL";  
            System.out.println("nextRight of "+ btc.root.left.left.data +"is "+d);  
      }  
 }
Output:

Comments

Post a Comment

Popular posts from this blog

Tournament Tree or Winner Tree

Image
Tournament Tree or Winner Tree :  Is a form of min(max) heap which is a complete binary tree. every external node represents a player and internal node represents a winner. Winner: select the best player among N palyers , (N -1) players to be eliminated. we need minimum of (N-1) games (comparisons). Second best player: we can pick second best player in (N + log2(n-2)) comparisons.   The above tree contains 4 leaf nodes that represent players and have 3 levels 0, 1 and 2. Initially 2 games are conducted at level 2, one between 5 and 3 and another one between 7 and 8. In the next move, one more game is conducted between 5 and 8 to conclude the final winner. Overall we need 3 comparisons. For second best player we need to trace the candidates participated with final winner, that leads to 7 as second best. Uses: Tree selection sort using tournament tree.  
Read more

Linked List

Image
single linked list: 1. Node class NodeLL.java package com.nrs.ds.basic; public class NodeLL { Object value; NodeLL next; public NodeLL(Object value,NodeLL next){ this.value=value; this.next = next; } } 2. LinkedList implementation LinkedListImpl.java package com.nrs.ds.basic; public class LinkedListImpl<T> { NodeLL head; public LinkedListImpl(){ head = null; } public void add(Object value){ NodeLL newNode= new NodeLL(value,null); if(head == null){ head=newNode; }else{ newNode.next = head; head = newNode; } } public void delete(){ head = head.next; } public void display(){ NodeLL n=head; while(n != null){ System.out.println((T)n.value); n = n.next; } } ...
Read more

Heaps

Image
 A Binary Heap is either Min Heap or Max Heap. Min Binary Heap: the key at root must be minimum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Min Binary Heap: The key at root must be maximum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree. Binamial Heap: Binamial Heap  is a Extention of Binary Heap that provides faster union or merge operations together with other operations provided by Binary Heap. Is a collection of tinomial trees. Binamial Tree Tree: A binomial Tree of order 0 has 1 node. A binomial Tree oder k can be constructed by taking two binomial trees of order k-1, and making one as leftmost child of other.  Binomial Heap: Is a set of Binomial Tree where each Binomial Tree follows Min Heap Property. and there can be at-most one Binomial Tree of any degree. Fibonacci Heap:  In terms of Time Com...
Read more