Author |
Topic: Loop in a BST (Read 2822 times) |
|
spur
Newbie
Gender: 
Posts: 47
|
 |
Loop in a BST
« on: Jul 18th, 2009, 9:32pm » |
 Quote  Modify
|
How to find if there is any loop in a BST without changing the structure of the tree...
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Loop in a BST
« Reply #1 on: Jul 19th, 2009, 12:55am » |
Quote Modify
|
Can you clarify what you mean by loop in BST?
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Loop in a BST
« Reply #2 on: Jul 19th, 2009, 3:14am » |
Quote Modify
|
I would assume he means some descendant has one of its ancestors as child. Which could happen if you allow for time travel. 
Any number of cycle-detection graph-algorithm would work. Although that's a bit over kill.
You could use a hash_map to keep track of which nodes you have visited already, and if in traversal you visit a child that was already visited before, then you must be in a loop.
|
| « Last Edit: Jul 19th, 2009, 3:21am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Loop in a BST
« Reply #3 on: Jul 19th, 2009, 1:23pm » |
Quote Modify
|
An in-order walk over the BST should do it. You just need to keep track of the recently seen key. If the node being visited have a key < last_key, then you have a loop in BST.
Code:
isLoop = false;
inorder(node *n)
{
if(isLoop)
return;
if(n == null)
return;
inorder(n->left); //edited
static int last_key = min_BST(); //initialize with minimum value in BST
if(n->data < last_key)
{ isLoop = true;
return;}
else
{ last_key = n->data; }//update last_key
inorder(n->right); //edited
}
|
|
min_BST() returns the least value stored in BST.
Here you must handle a special case separately, which is, when there is a loop in the left-most branch of the BST. If there is, the above function will go in infinite recursion. Also min_BST() won't be able to find the minimum value stored in BST. So once this case is handled separately, and you have ensured that there is no loop in left-most branch, we can run this algo, to find the presence of a loop.
|
| « Last Edit: Jul 20th, 2009, 3:18am by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
spur
Newbie
Gender:
Posts: 47
|
|
Re: Loop in a BST
« Reply #4 on: Jul 20th, 2009, 2:41am » |
Quote Modify
|
In the above post i have the following doubts..
1) what does the line "node(n->left);" do.
2) last_key was initialized with min_BST(); but in the very next line the if statement fails and last_key value is reassinged.. so what is the purpose of initializing it.
3) why is the leftmost node treated separately.
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Loop in a BST
« Reply #5 on: Jul 20th, 2009, 3:22am » |
Quote Modify
|
on Jul 20th, 2009, 2:41am, spur wrote:
1) what does the line "node(n->left);" do.
|
|
Sorry, that was typing mistake, i've corrected it.
Quote:
2) last_key was initialized with min_BST(); but in the very next line the if statement fails and last_key value is reassinged.. so what is the purpose of initializing it.
|
|
last_key is a static variable, it'll be initialized only once.
Quote:
3) why is the leftmost node treated separately.
|
|
if there is a loop in leftmost branch, i.e. if some node who's in the leftmost branch of the tree, have a left-child pointer pointing to its ancestor then the in-order function call will go in infinite recursion.
|
| « Last Edit: Jul 20th, 2009, 5:05am by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Loop in a BST
« Reply #6 on: Jul 20th, 2009, 5:08am » |
Quote Modify
|
Ahh!!! Scrap the above approach. It will go in infinite recursion. Hash-map is a fool-proof idea, still thinking if it is the best.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Loop in a BST
« Reply #7 on: Jul 20th, 2009, 5:19am » |
Quote Modify
|
You can probably use the same approach as for finding the loop in a linked list. Having two pointers, one traversing at twice the rate. You'll need to use an explicit stack for the traversal though.
It's more memory efficient. Additionally, it doesn't matter if you have a BST or merely a BT. (Well, ok, that's true for the hash-table solution as well)
If every value only occurs once, though, I don't see why it would be a problem to find the first value that is out of place. And this you could do recursively.
Code:is_loopless_bst(min, max, root)
{
if (root==null)
return true;
if(min < root->value < max)
return is_loopless_bst(min, root->value, root->left) && is_loopless_bst(root->value, max, root->right);
else
return false;
}
//call with: is_loopless_bst(-inf, inf, tree)
|
|
(PS, actually, it just checks whether it is a BST; but that's sufficient under these constraints)
|
| « Last Edit: Jul 20th, 2009, 5:27am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
raghu_nx
Newbie
Posts: 5
|
|
Re: Loop in a BST
« Reply #8 on: Jul 21st, 2009, 2:07am » |
Quote Modify
|
@towr
(PS, actually, it just checks whether it is a BST; but that's sufficient under these constraints)
There can be a loop in the bst and still obey the binary search tree constraints. For ex, node A right child's right child left pointer poiniting back to A. i.e
A->right->right->left=A;
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Loop in a BST
« Reply #9 on: Jul 21st, 2009, 2:49am » |
Quote Modify
|
on Jul 21st, 2009, 2:07am, raghu_nx wrote:@towr
(PS, actually, it just checks whether it is a BST; but that's sufficient under these constraints)
There can be a loop in the bst and still obey the binary search tree constraints. For ex, node A right child's right child left pointer poiniting back to A. i.e
A->right->right->left=A; |
|
I think you missed the part about constraints. I stated up front that the BST is not allowed to contain doubles, so it can't contain A twice.
|
| « Last Edit: Jul 21st, 2009, 2:51am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
raghu_nx
Newbie
Posts: 5
|
|
Re: Loop in a BST
« Reply #10 on: Jul 21st, 2009, 8:53am » |
Quote Modify
|
Quote:I think you missed the part about constraints. I stated up front that the BST is not allowed to contain doubles, so it can't contain A twice.
|
|
Sorry may be i am not clear or my understanding is incorrect. Even though all the elements are unique, presence of a loop implies that one element is repeated. In the example i gave A->right->right->left=A, i was showing the presence of a loop starting at A. In this case, the function is_loopless_bst doesnt give the correct answer is my understanding. Please correct me if i am wrong.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Loop in a BST
« Reply #11 on: Jul 21st, 2009, 9:58am » |
Quote Modify
|
on Jul 21st, 2009, 8:53am, raghu_nx wrote:| Sorry may be i am not clear or my understanding is incorrect. Even though all the elements are unique, presence of a loop implies that one element is repeated. |
|
Yeah, and then it fails the test because under the rules it doesn't qualify. You don't have A<A, and A isn't null, so it can only return false. And therefore you know it must have a loop.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
raghu_nx
Newbie
Posts: 5
|
|
Re: Loop in a BST
« Reply #12 on: Jul 21st, 2009, 11:13am » |
Quote Modify
|
yeah got it.. thanks..
|
|
IP Logged |
|
|
|
bazinga
Junior Member
Gender:
Posts: 53
|
|
Re: Loop in a BST
« Reply #13 on: Aug 31st, 2009, 11:56pm » |
Quote Modify
|
Quote:| You can probably use the same approach as for finding the loop in a linked list. Having two pointers, one traversing at twice the rate. You'll need to use an explicit stack for the traversal though. |
|
Towr can you explain it in more detail(like by giving some pseudocode).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Loop in a BST
« Reply #14 on: Sep 15th, 2009, 4:47am » |
Quote Modify
|
on Aug 31st, 2009, 11:56pm, joshi.prahlad wrote:
Towr can you explain it in more detail(like by giving some pseudocode). |
|
Based on this post
Code:node* next(node *cur, stack& st)
{
if(cur->left)
{
st.push(cur->right)
return cur->left
}
else if ( !st.empty() )
return st.pop();
else
return NULL;
}
node* find_loop( node * root) // assuming there is a loop, otherwise check for there not being a next;
{
stack st1, st2;
node* pt1, pt2;
pt1 = root;
pt2 = next(root, st2);
while (pt1 != pt2)
{
pt1 = next(pt1, st1);
pt2 = next(next(pt2, st2), st2);
}
pt1 = root;
pt2 = next(pt2, st2);
while (pt1 != pt2)
{
pt1 = next(pt1, st1);
pt2 = next(pt2, st2);
}
return pt1;
}
|
|
The next() function lets you approach the tree as a linked list (in this case of nodes in preorder). Thus reducing the problem of finding a loop in a tree to finding a loop in a linked list.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
gt
Newbie
Posts: 13
|
|
Re: Loop in a BST
« Reply #15 on: Sep 15th, 2009, 6:18am » |
Quote Modify
|
why cant we use classic algorithm that tests whether a given binary tree is a binary search tree or not ...
in this algorithm we start with -INFINITY, +INFINITY at the root...... let us call this pair ... X,Y
every time we move left at N...
X, Y= value of node N ... like N.data
every time we move right at N...
X= N.data, Y
the constraint being value at each node should be between X and Y...
if at any point we found a node violating this rule...
we can declare there is a loop in a BST right 
correct me if am wrong...
time complexity : O(n) --- no of nodes in a tree
|
|
IP Logged |
|
|
|
gt
Newbie
Posts: 13
|
|
Re: Loop in a BST
« Reply #16 on: Sep 15th, 2009, 6:23am » |
Quote Modify
|
Oh my goddamn..
@ .towr i didnt notice ur post at all..
i looked at the question... then felt lazy to read through the discussion...
so gave my solution...
i framed this solution sometime back during class hours... so was anxious to post it to say the truth
|
|
IP Logged |
|
|
|
bazinga
Junior Member
Gender:
Posts: 53
|
|
Re: Loop in a BST
« Reply #17 on: Sep 17th, 2009, 7:11am » |
Quote Modify
|
Quote:
The next() function lets you approach the tree as a linked list (in this case of nodes in preorder). Thus reducing the problem of finding a loop in a tree to finding a loop in a linked list.
|
|
thanks a lot tower.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print