One best question in my sem-III DSF paper was
Iterative Solution For Inorder TraversalI was not prepare for it, but i was knowing the recursive way of traversing the BST tree so i applied the same concept and find out a algo in 25 minutes sadly in 5 minutes or even less i couldn't complete that question and my ma'am snatch the paper, coz the time was 5:30 pm duhh!!
And after examz i came home and implemented that algo and it was 100% perfect solution for iterative way of Tree traversal , today i m gonna show that to you .......
The thing you must note, in the Stack implementation is that it does not store the data it store the refrence i.e a Node which inturn contains the data.
package datastructurepractice.BST;
/**
*
* @author Naved Momin
*/
class StackNode
{
Node data;
StackNode next;
}
public class StackForBST {
StackNode top;
public void push( Node x ){
if( x != null )
{
StackNode newrec = new StackNode();
newrec.data = x;
newrec.next = null;
if( top == null)
top = newrec;
else
{
newrec.next = top;
top = newrec;
}
}
}
public void display( ){
System.out.println( "stack display");
if( isempty() )
System.out.println(" empty stack ....");
StackNode n = top;
while( n != null){
Node r = n.data;
System.out.print (r.data + " ");
n = n.next;
}
}
boolean isempty( ){
if( top == null)
return true;
else
return false;
}
Node stacktop( ){
if( top != null )
return top.data;
else
return null;
}
public Node pop( ){
if( !isempty() ){
Node x = top.data;
top = top.next;
return x;
}else{
System.out.println( "stack out of data");
System.exit(0);
return null;
}
}
}
package datastructurepractice.BST;
import java.util.Calendar;
import java.util.Scanner;
/**
*
* @author Naved Momin
*/
class Node{
int data;
boolean lV = false, rV = false;
Node left, right;
}
public class BST {
Node root;
private long start;
private long end;
public void travInorder( ){
inorder(root);
}
public void insert( int x ){
Node newrec = new Node();
newrec.data = x;
newrec.left = null;
newrec.right = null;
if( root == null){
root = newrec;
}
else{
Node a, b;
a = b = root;
while( a != null ){
b = a;
if( x < a.data ){
a = a.left;
}else{
a = a.right;
}
}
if( x <= b.data ){
b.left = newrec;
}else{
b.right = newrec;
}
}
}
public void displayInorder( ){
System.out.println( "inorder recurssive ");
long start1 = Calendar.getInstance().getTimeInMillis();
inorder(root);
long end1 = Calendar.getInstance().getTimeInMillis();
System.out.println( "total time taken (Recursive)" + (end1 - start1 ) + " ms");
System.out.println( "inorder iterative ");
start = Calendar.getInstance().getTimeInMillis();
inOrderIterative(root);
}
public void delete( ){
System.out.println( "enter value ot be deleted");
int v = new Scanner(System.in).nextInt();
Node a, b ;
a = b = root;
while( a != null && a.data != v){
b = a;
if( v < a.data )
a = a.left;
else
a = a.right;
}
if( a == null )
System.out.println( "i could not find the value");
else{
if( a.left != null && a.right == null){
if( root == a){
root = a.left;
}else{
if( a == b.left){
b.left = a.left;
}else{
b.right = a.left;
}
}
}
else if( a.right != null && a.left == null ){
if( root == a){
root = a.right;
}else if( b.right == a){
b.right = a.right;
}else{
b.left = a.right;
}
}else if( a.right == null && a.left == null){
if( root == a){
root = null;
}else if( b.right == a){
b.right = null;
}else{
b.left = null;
}
}else if( a.right != null && a.left != null){
Node c = a.right;
while (c.left != null) {
c = c.left;
}
c.left = a.left;
if( a == root){
root = a.right;
}else {
if( b.left == a)
b.left = a.right;
else
b.right = a.right;
}
}
System.out.println( "deleted node = " + v) ;
}
}
boolean isempty( ){
if( root == null)
return true;
else
return false;
}
public void inOrderIterative( Node root ){
StackForBST s = new StackForBST();
s.push(root);
while (true) {
Node r = s.stacktop();
while( r.lV && r.rV ){
s.pop();
r = s.stacktop();
if( r == null ){
end = Calendar.getInstance().getTimeInMillis();
System.out.println( "total time taken (Iterative)" + (end - start ) + " ms");
System.exit(0);//when stack becomes empty
}
}
if( !r.lV){
while( r.left != null){
r.lV = true;
r = r.left;
s.push(r);
}
}
r.lV = true;
System.out.print(r.data + " ");
if( r.lV == true && r.rV == false && r.right != null){
r.rV = true;
r = r.right;
s.push(r);
}else{
r.rV = true;
}
}
}
public void inorder( Node root ){
if( root != null ){
inorder(root.left);
System.out.print( root.data + " ");
inorder(root.right);
}
}
public static void main(String[] args) {
// TODO code application logic here
}
}
//Output
run:
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
11111
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
22222
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
333333
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
444444
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
666666
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
555555
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
5656
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
4545
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
2323
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
1212
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
8989
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
45457
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
23235
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
454545
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
232345
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
12214
enter 1 for insert 2 for delete 3 for display 4 for exits
122
exits command executed
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
444
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
55
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
32
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
1
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
2
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
4
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
5
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
6
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
7
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
8
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
9
enter 1 for insert 2 for delete 3 for display 4 for exits
1
enter no
10
enter 1 for insert 2 for delete 3 for display 4 for exits
3
inorder recurssive
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666
total time taken (Recursive)3 ms
inorder iterative
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666
total time taken (Iterative)13 ms
From this it looks like recursive approach is faster than iterative approach.......Hence we have proved that recursion is not always slow, there are some problems which are best solved(In terms of performance & simplicity) by "RECURSION".
Trace the code to get the algo. and slight modification will give you preorder & postorder....GL.
No comments:
Post a Comment