Find whether two BST are the same. Recursively and Iteratively

View previous topic View next topic 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

View previous topic View next topic Back to top

- Similar topics

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