wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Distance in a Binary Tree 
        
(Message started by: Dudidu on Oct 13th, 2003, 10:33am)
Title: Distance in a Binary Tree
Post by Dudidu on Oct 13th, 2003, 10:33am
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).
Title: Re: Distance in a Binary Tree
Post by towr on Oct 13th, 2003, 11:10am
1 ::[hide]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.[/hide]::

Does the second one need to be O(1) memory as well?
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 14th, 2003, 12:57am

on 10/13/03 at 11:10:40, towr wrote:
1 ::[hide]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.[/hide]::

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: [hide] 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)). [/hide]
    [2] In the second part only O(1) memory can be used as well (sorry...).
Title: Re: Distance in a Binary Tree
Post by towr on Oct 14th, 2003, 3:42am

on 10/14/03 at 00:57:31, Dudidu wrote:
    [1] The solution to the first part can be more efficient - Hint: [hide] <hidden>[/hide]
Then I suppose in each node the parent has to be known (which isn't necessarily the case in a binary search tree).
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 14th, 2003, 3:51am
Yes, I'm sorry if that wasn't understandable  :-/.
Moreover, this is also true for the second part.
Title: Re: Distance in a Binary Tree
Post by towr on Oct 14th, 2003, 4:45am
then for one,
::[hide]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
[/hide]::
I think..
I'll have to think abit more about the second problem..
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 14th, 2003, 5:52am
Well done towr !!!  :D
This, of course, has a O(d(p1,p2)) time complexity (as desired).
Good luck with the next one !!!
Title: Re: Distance in a Binary Tree
Post by James Fingas on Oct 14th, 2003, 12:47pm
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:
[hide]
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. [/hide]
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 16th, 2003, 4:19pm

on 10/14/03 at 12:47:21, 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: [hide] O(d(p1,p2)) (i.e. the same result as for the first part) [/hide]
Good luck !!!
Title: Re: Distance in a Binary Tree
Post by Rezyk on Oct 16th, 2003, 5:34pm
How about [hide]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)).[/hide]
Title: Re: Distance in a Binary Tree
Post by towr on Oct 16th, 2003, 11:31pm
if the height of a node is known, [hide]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..[/hide]
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 19th, 2003, 1:26am

on 10/16/03 at 17:34:14, Rezyk wrote:
How about ...

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 [hide] alternating upward traversals [/hide]are done (and how this algorithm satisfies the desired time complexities). Thanks...
Title: Re: Distance in a Binary Tree
Post by DH on Oct 20th, 2003, 2:02am
-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 :

::
[hide]

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++;
      }
}
[/hide]
::
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 20th, 2003, 3:40am

on 10/20/03 at 02:02:15, 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...
Title: Re: Distance in a Binary Tree
Post by DH on Oct 20th, 2003, 4:38am

on 10/20/03 at 03:40:13, 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).
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 20th, 2003, 5:14am

on 10/20/03 at 04:38:41, 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).
Title: Re: Distance in a Binary Tree
Post by towr on Oct 20th, 2003, 6:01am
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..
Title: Re: Distance in a Binary Tree
Post by Rezyk on Oct 20th, 2003, 11:11am
Here's code to get the [hide]difference in heights[/hide] for the second part:

[hide]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)).
[/hide]
Title: Re: Distance in a Binary Tree
Post by Dudidu on Oct 22nd, 2003, 2:23am

on 10/20/03 at 11:11:36, Rezyk wrote:
Here's code to get the [hide]difference in heights[/hide] for the second part:

Rezyk, Bravo ;D !!!
I've reviewed your answer and its absolutly correct !


---------------------------------------------------
To anyone which have an interest - all of this threads
questions have been answered.
---------------------------------------------------  


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board