Find whether two BST are the same. Recursively and Iteratively
Page 1 of 1
Find whether two BST are the same. Recursively and Iteratively
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;
}
}
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;
}
}
Re: Find whether two BST are the same. Recursively and Iteratively
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);
}
}
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);
}
}
Similar topics
» Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).
» Find if a singly linked List has loop or not. How to find out middle element from a looped single linked list
» Find the height of BST
» To find the successor of x in a BST
» Given a string, find all of its permutations
» Find if a singly linked List has loop or not. How to find out middle element from a looped single linked list
» Find the height of BST
» To find the successor of x in a BST
» Given a string, find all of its permutations
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|