Author |
Topic: Binary Search Tree Problem (Read 864 times) |
|
Bala69
Newbie
Gender: 
Posts: 5
|
 |
Binary Search Tree Problem
« on: Nov 15th, 2011, 4:01am » |
 Quote  Modify
|
Given two BST's A and B, we need to check whether A has all the elements of B, they may not have an identical structure. O( nlogn) is obvious. Interviewer is looking for a better solution. Can anyone please help me out here.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary Search Tree Problem
« Reply #1 on: Nov 15th, 2011, 8:52am » |
Quote Modify
|
Move through them in-order. You could wrap them in a stream object, then compare those as you would simple lists.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Bala69
Newbie
Gender:
Posts: 5
|
|
Re: Binary Search Tree Problem
« Reply #2 on: Nov 15th, 2011, 10:50pm » |
Quote Modify
|
Can we do without extra space for lists, while traversing itself as they are BST's.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Binary Search Tree Problem
« Reply #3 on: Nov 16th, 2011, 10:03pm » |
Quote Modify
|
Preferably you'd want a stack to move through the trees (so you can easily jump to the next subtree when you've finished the current one). Though if I recall correctly you can do it with only constant extra space, but that would also mean temporarily changing the links in the tree.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Roman
Newbie
Posts: 2
|
|
Re: Binary Search Tree Problem
« Reply #4 on: Nov 16th, 2011, 10:24pm » |
Quote Modify
|
If BST's can be modified, both BST's can be converted into DLLs in O(n), then you can compare these lists in linear time.
|
|
IP Logged |
|
|
|
Bala69
Newbie
Gender:
Posts: 5
|
|
Re: Binary Search Tree Problem
« Reply #5 on: Nov 16th, 2011, 11:05pm » |
Quote Modify
|
Hint i got from interviewer was
1. Using Recursion
2. Resume search from prev result.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Binary Search Tree Problem
« Reply #6 on: Nov 24th, 2011, 3:08pm » |
Quote Modify
|
What about this: (pseudo-code)
boolean includes_tree(node a, node b)
{
if( b==null ) return true;
if( a==null ) return false;
if( b.value==a.value)
return includes_tree(a.left, b.left) && includes_tree(a.right, b.right);
if( b.value<a.value){
return includes_tree(a.left, b.left) && includes_value(a.left, b.value) && includes_tree(a, b.right);
} else {
return includes_tree(a, b.left) && includes_value(a.right, b.value) && includes_tree(a.right, b.right);
}
}
boolean includes_value(node a, int v)
{
while( a!=null ){
if( v==a.value ) return true;
if( v<a.value ) a = a.left;
else a = a.right;
}
return false;
}
I think it should be faster than O(n log n) but I am not sure about the worst case.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print