Author |
Topic: Distance in a Binary Tree (Read 5118 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Distance in a Binary Tree
« on: Oct 13th, 2003, 10:33am » |
 Quote  Modify
|
Since the CS section seems to be quite deserted, lets try to revive it  :
- You are given 2 pointers to two nodes (p1, p2) in a binary search tree1. Devise an algorithm to find the distance between p1 and p2 (i.e. the length of the shortest path between them).
You may use O(1)2 additional memory and you must not change the structure of the tree.
- Devise an algorithm to the same problem when the tree is ("just") binary (i.e. not a binary search tree).
1 A binary search tree is a binary tree which each node of it has the following properties:
(-) For every nodes y in left subtree of x, key[y] < key[x]
(-) For every nodes y in right subtree of x, key[y] > key[x]
2 O(1) additional memory indicates that a constant amount of additional memory can be used (e.g. memory consumption that is dependent on the size of the tree (or on the distance between the pointers) is not legal).
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Distance in a Binary Tree
« Reply #1 on: Oct 13th, 2003, 11:10am » |
Quote Modify
|
1 ::Starting from the root you can easily go to the node where the paths to the given nodes split, and then it's simple enough to add the path lengths from that point onwards.::
Does the second one need to be O(1) memory as well?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #2 on: Oct 14th, 2003, 12:57am » |
Quote Modify
|
on Oct 13th, 2003, 11:10am, towr wrote:1 ::Starting from the root you can easily go to the node where the paths to the given nodes split, and then it's simple enough to add the path lengths from that point onwards.::
Does the second one need to be O(1) memory as well? |
|
towr hi,
I have two remarks:
[1] The solution to the first part can be more efficient - Hint: It should be O(d(p1,p2)) (i.e. proportional to the distance between them) - in your solution it may be depandent on the distance of p1 and p2 from the root (which may cause the algorithm to run in O(n) (i.e. proportional to the number of elements in the tree)).
[2] In the second part only O(1) memory can be used as well (sorry...).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Distance in a Binary Tree
« Reply #3 on: Oct 14th, 2003, 3:42am » |
Quote Modify
|
on Oct 14th, 2003, 12:57am, Dudidu wrote:[1] The solution to the first part can be more efficient - Hint: <hidden> |
|
Then I suppose in each node the parent has to be known (which isn't necessarily the case in a binary search tree).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #4 on: Oct 14th, 2003, 3:51am » |
Quote Modify
|
Yes, I'm sorry if that wasn't understandable  .
Moreover, this is also true for the second part.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Distance in a Binary Tree
« Reply #5 on: Oct 14th, 2003, 4:45am » |
Quote Modify
|
then for one,
::take ln as the lowest value node, and hn as the high value node,
Node cn=ln;
int c=0;
while (cn != root && cn.parent < hn)
cn = cn.parent
c++;
endwhile
while (cn != hn)
cn = cn > hn ? cn.left : cn.right;
c++;
endwhile
::
I think..
I'll have to think abit more about the second problem..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #6 on: Oct 14th, 2003, 5:52am » |
Quote Modify
|
Well done towr !!! 
This, of course, has a O(d(p1,p2)) time complexity (as desired).
Good luck with the next one !!!
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Distance in a Binary Tree
« Reply #7 on: Oct 14th, 2003, 12:47pm » |
Quote Modify
|
The simplest way to solve the second part would be just to trace your way up the tree to the root from each node. Since there's no presumed ordering in the tree, this seems to be optimal:
Fundamental result: we must traverse to the root node. Otherwise we have no idea where the nodes are in relation to each other, and it would take O(d(p1,p2)2) time to determine the distance, which I presume is larger than O(N).
Trace back to the top of the tree from each node, recording the left and right subtrees as 0 and 1 in a binary string. Compare the binary strings. The sum of the lengths of the two minus twice the length of the common parts at the end gives the distance.
To do this with constant memory, we could record the difference in depths, then pre-traverse that difference from the deeper node, and traverse the rest of the way up to the root in parallel, taking O(1) space and O(N) time. When the two paths meet, we can compute the distance.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #8 on: Oct 16th, 2003, 4:19pm » |
Quote Modify
|
on Oct 14th, 2003, 12:47pm, James Fingas wrote:| The simplest way to solve the second part would be just to trace your way up the tree to the root from each node. Since there's no presumed ordering in the tree, this seems to be optimal... Fundamental result: we must traverse to the root node. |
|
James Hi,
Unfortunatly I disagree with your "Fundamental result" and although your algorithm is quite efficient (O(n)), There is an algorithm that works better - Hint: O(d(p1,p2)) (i.e. the same result as for the first part)
Good luck !!!
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Distance in a Binary Tree
« Reply #9 on: Oct 16th, 2003, 5:34pm » |
Quote Modify
|
How about you start off doing 2 parallel upward traversals? But on the jth iteration, if j is a power of 2, you retrace p1's traversal back from p1 just to see if it intersects the current head of p2's traversal -- and also vice versa, retracing p2's traversal.
You should find a intersection by 2d(p1,p2) iterations; at that point you can deduce height(p1)-height(p2). From there you can finish the same way James' algorithm does.
The time spent retracing should total no more than O(total iterations)=O(d(p1,p2)).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Distance in a Binary Tree
« Reply #10 on: Oct 16th, 2003, 11:31pm » |
Quote Modify
|
if the height of a node is known, we can first go up from one node to th height of the other, and then go up in both paths till they reach the same node..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #11 on: Oct 19th, 2003, 1:26am » |
Quote Modify
|
on Oct 16th, 2003, 5:34pm, Rezyk wrote:
Rezyk Hi,
Your solution seems to be in the right direction  , but can you be more specific about the how the algorithm actually works, i.e. how the alternating upward traversals are done (and how this algorithm satisfies the desired time complexities). Thanks...
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Distance in a Binary Tree
« Reply #12 on: Oct 20th, 2003, 2:02am » |
Quote Modify
|
-towr,
It seems to me that the first loop of your algorithm may trace back all the way to the root node and this is not O(d(p1,p2)). Am I missing something ?
In my opinion the solution for problem 1 shoud look like this :
::
Node cn1=ln,cn2=ln;
int d_up=0,d=0;
while (cn2!=hn)
{
if (cn1!=NULL)
{
if (cn1->parrent!=NULL)
{
int cmp=(cn1->parrent->key > cn1->key)
cn1=cn1->parrent;
d_up++;
if (cmp)
{
if (hn->key > cn1->key)
{
cn2=cn1;
d=d_up;
continue;
}
else
cn1=NULL;
}
}
else
cn1=NULL;
}
if (cn2!=NULL)
{
cn2=(hn->key > cn2->key) ? cn2->right : cn2->left;
d++;
}
}
::
|
| « Last Edit: Oct 20th, 2003, 2:04am by DH » |
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #13 on: Oct 20th, 2003, 3:40am » |
Quote Modify
|
on Oct 20th, 2003, 2:02am, DH wrote:-towr,
It seems to me that the first loop of your algorithm may trace back all the way to the root node and this is not O(d(p1,p2)). Am I missing something ? |
|
DH Hi,
towr's algorithm might trace back to the root but this only happens if the root is the least common ancestor (LCA) of p1 and p2, and thus must be on the shortest path from p1 to p2 (o/w the trace-back will stop before reaching the root).
Hope that this helps...
|
|
IP Logged |
|
|
|
DH
Newbie
Gender:
Posts: 19
|
|
Re: Distance in a Binary Tree
« Reply #14 on: Oct 20th, 2003, 4:38am » |
Quote Modify
|
on Oct 20th, 2003, 3:40am, Dudidu wrote:
DH Hi,
towr's algorithm might trace back to the root but this only happens if the root is the least common ancestor (LCA) of p1 and p2, and thus must be on the shortest path from p1 to p2 (o/w the trace-back will stop before reaching the root).
Hope that this helps...
|
|
Hi,
Consider the following case:
hn=the maximum key in the tree
ln=maximum key in (tree - hn)
hn is the right child of ln
d(ln,hn)=1. The first loop will trace back to the root and the root is not LCA(ln,hn).
|
|
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #15 on: Oct 20th, 2003, 5:14am » |
Quote Modify
|
on Oct 20th, 2003, 4:38am, DH wrote:
Consider the following case... |
|
DH, Well Done !
You are right, The algorithm should be adjusted to check if in the initial state we haven't reached (i.e. started with) the LCA already (which is ln).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Distance in a Binary Tree
« Reply #16 on: Oct 20th, 2003, 6:01am » |
Quote Modify
|
reconsidering my algorithm, I don't think that's the only problem with it :P
Of course that's what you get if you don't test it (or otherwise properly evaluate it)
But the general idea works for most cases, and the exception is easily treated seperately..
|
| « Last Edit: Oct 20th, 2003, 6:03am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Distance in a Binary Tree
« Reply #17 on: Oct 20th, 2003, 11:11am » |
Quote Modify
|
Here's code to get the difference in heights for the second part:
if (p1==p2) return 0;
n = 1;
while (true) {
p1ancestor = p1;
p2ancestor = p2;
for (i = 0; i<n; i++) p1ancestor = p1ancestor.parent;
for (i = 0; i<n; i++) {
if (p1ancestor==p2ancestor) return n-i;
p2ancestor = p2ancestor.parent;
}
p1ancestor = p1;
for (i = 0; i<n; i++) {
if (p1ancestor==p2ancestor) return i-n;
p1ancestor = p1ancestor.parent;
}
if (p1ancestor==p2ancestor) return 0;
n = 2*n;
}
Let x = max(d(p1,LCA(p1,p2)),d(p2,LCA(p1,p2))) = O(d(p1,p2)). The loop should return when 2x>n>=x. Since n doubles every time and the inner loop runs in O(n) time, the overall time is given by O(2x)+O(x)+O(x/2)+O(x/4)... = O(2x) = O(d(p1,p2)).
|
| « Last Edit: Oct 20th, 2003, 11:16am by Rezyk » |
IP Logged |
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Distance in a Binary Tree
« Reply #18 on: Oct 22nd, 2003, 2:23am » |
Quote Modify
|
on Oct 20th, 2003, 11:11am, Rezyk wrote:| Here's code to get the difference in heights for the second part: |
|
Rezyk, Bravo  !!!
I've reviewed your answer and its absolutly correct !
---------------------------------------------------
To anyone which have an interest - all of this threads
questions have been answered.
---------------------------------------------------
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print