Find whether two BST are the same. Recursively and Iteratively

Go down

Find whether two BST are the same. Recursively and Iteratively

Post  Admin on Wed Aug 24, 2011 11:13 pm

Recursively:

public boolean checkBST(TreeNode n1, TreeNode n2){
if(n1==null&&n2==null)
return true;
else if(n1==null||n2==null)
return false;
else{
if(n1.value==n2.value){
return checkBST(n1.left,n2.left)&&checkBST(n1.right,n2.right);
}
else
return false;
}
return true;
}


Iteratively:

public boolean checkTree(TreeNode n1, TreeNode n2){
Stack<TreeNode> st1=new Stack<TreeNode>();
Stack<TreeNode> st2=new Stack<TreeNode>();
if(n1==null&n2==null)
return true;
else if(n1==null||n2==null)
return false;
else{

st1.put(n1);
st2.put(n2);
while(!st1.isEmpty()&&(!st2.isEmpty())){
TreeNode temp1=st1.pop();
TreeNode temp2=st2.pop();
if(temp1!=temp2)
return false;
if(temp1.left&&temp2.left){
st1.put(temp1.left);
st2.put(temp2.left);
}
else if(temp1.right||temp2.right){
return false;
}
if(temp1.right&&temp2.right){
st1.put(temp1.right);
st2.put(temp2.right);
}
else if(temp1.right||temp2.right)
return false;
}
return true;
}
}

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Re: Find whether two BST are the same. Recursively and Iteratively

Post  Admin on Thu Aug 25, 2011 3:29 pm

Iterative way ofr single preorderTraversal

public void preorderTraversal(Node root){
Stack stack=new Stack();
stack.push(root);
while(true){
Node current=stack.pop();
if(current==null) break;
Node right=current.getRight();
if(right!=null)
stack.push(right);
Node left=current.getLeft();
if(left!=null)
stack.push(left);
}
}

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum