Would this solution be important? Is it already solved?

[Mountain]

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

First, we start with a general tree (any of the trees that my data
structures book calls rooted trees or unordered trees). Then we are
given two specific nodes (Na and Nb) that belong to that tree.

We would like to know if the second node (Nb) is an ancestor of the
first node (Na).

My question to the group is this:

If there was an algorithm for answering this question _without_
traversing the tree or doing any type of search or any
iterative/recursive operations, how important and useful would that be?
Obviously, it would save a lot of computing time.

Is there a known solution that does this? Or is there a proof that it
cannot be done?

Are there any citations I should be looking at? Any help is appreciated.

 

[Willem]

Mountain wrote:
) I would like opinions on whether this solution could be important and
) whether anyone knows if it is already solved. (I would also like to
) know if anyone thinks it cannot be solved.)
)
) First, we start with a general tree (any of the trees that my data
) structures book calls rooted trees or unordered trees). Then we are
) given two specific nodes (Na and Nb) that belong to that tree.
)
) We would like to know if the second node (Nb) is an ancestor of the
) first node (Na).
)
) My question to the group is this:
)
) If there was an algorithm for answering this question _without_
) traversing the tree or doing any type of search or any
) iterative/recursive operations, how important and useful would that be?
) Obviously, it would save a lot of computing time.

I think you're going to have to specify in a lot more detail what is and
is not allowed. For example, 'no iterative/recursive operations' excludes
all algorithms possible, except maybe hello world.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[wkaras]

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

First, we start with a general tree (any of the trees that my data
structures book calls rooted trees or unordered trees). Then we are
given two specific nodes (Na and Nb) that belong to that tree.

We would like to know if the second node (Nb) is an ancestor of the
first node (Na).

My question to the group is this:

If there was an algorithm for answering this question _without_
traversing the tree or doing any type of search or any
iterative/recursive operations, how important and useful would that be?
Obviously, it would save a lot of computing time.

Is there a known solution that does this? Or is there a proof that it
cannot be done?

Are there any citations I should be looking at? Any help is appreciated.

If I were faced with this problem (hasn't happen so far in 20+ years of
programming), I would either implement the tree with parent pointers,
or maybe store the tree in an array where the entries whose indexes
are 2N and 2N+1 are the children in the tree of the entry whose array
index is N. But both of these approaches have drawbacks, so another
approach would be worth looking at. Don't think you'd be able to
retire
in Tahiti on the patent royalties, though.

 

[Alf P. Steinbach]

* Mountain:

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

First, we start with a general tree (any of the trees that my data
structures book calls rooted trees or unordered trees). Then we are
given two specific nodes (Na and Nb) that belong to that tree.

We would like to know if the second node (Nb) is an ancestor of the
first node (Na).

My question to the group is this:

If there was an algorithm for answering this question _without_
traversing the tree or doing any type of search or any
iterative/recursive operations, how important and useful would that be?

Not very useful, I think, since for a balanced tree the time to traverse
all the way up to the root is O(log n), where n is the number of nodes.

Obviously, it would save a lot of computing time.

Some cases of Nb actually /not/ an ancestor of Na, for arbitrary Nb and
Na, can easily be determined in constant time.

AFAIK you can not determine in constant time that Nb /is/ an ancestor
node, in the general case.

However, for specific cases with limited number of nodes you can do
things like that. For example, for a balanced in-memory binary tree the
path to any node can be represented as a sequence of bits. With 32-bit
memory addresses this sequence will never be 32 bits or larger (the
nodes wouldn't fit in available memory), and so a simple check of common
start sequence, just a few machine code instructions, determines
ancestorship.

Is there a known solution that does this?

See above.

Or is there a proof that it cannot be done?

For the general case the problem is to determine whether a path A of
N-way choices is a proper left substring of another such path B, with
the paths chosen arbitrarily.

If path A is longer or of equal length than B, then A cannot be a proper
left substring of B; that's one of the cases of "not ancestor".

If path A's first element is different from path B's first element, then
A cannot be a proper left substring of B; that's another such case.

There may be other such negative cases.

Otherwise, to check this in constant time, one would have to encode any
path in a unique small value or fixed small set of values, such that
those encodings could be compared for left-substring relationship in
constant time, and I don't think that's possible.

Are there any citations I should be looking at? Any help is appreciated.

Google.

 

[Tom Widmer]

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

First, we start with a general tree (any of the trees that my data
structures book calls rooted trees or unordered trees). Then we are
given two specific nodes (Na and Nb) that belong to that tree.

Does a node contain a pointer to its parent? Define exactly what your
data structure looks like.

We would like to know if the second node (Nb) is an ancestor of the
first node (Na).

My question to the group is this:

If there was an algorithm for answering this question _without_
traversing the tree or doing any type of search or any
iterative/recursive operations, how important and useful would that be?
Obviously, it would save a lot of computing time.

Well, if you've got a parent pointer in each node it is a trivial
O(depth) algorithm. If you don't have parent pointers, then an algorithm
that is better than O(n) might be of interest.

Is there a known solution that does this? Or is there a proof that it
cannot be done?

It would be useful if you accurately defined the problem you are trying
to solve first, otherwise a proof is impossible.

Tom

 

[Mountain]

Here is some more detail:
Traversing the tree node-by-node is not allowed -- that is obviously a
recursive or iterative operation. The solution should use only the two
nodes that are presented (what I called nodes Na and Nb) to determine
if Nb is an ancestor of Na. The solution must be general - it should
work on any of the types of trees I mentioned.

The solution should be quick - ideally just a very simple/fast
computation of some type. It cannot be a search. This means the
solution cannot involve searching the tree itself, nor can it involve
search a list inside each node, for example. It should not involve any
additional storage - meaning it cannot rely upon something like an
external index (the utilization of which would effectively be a search
anyway) or extra data related to each node.

The solution should be fundamentally simple, quick and not a gimmick.

 

[Mountain]

Hello Alf P. Steinbach. Thank you very much. Your reply was helpful. It
sounds like the solution I have in mind may not be completely unknown
or original. I'll work with it a bit more and see if it indeed
generalizes better or have any other especially redeeming qualities

 

[Mountain]

Don't think you'd be able to retire in Tahiti on the patent royalties, though.
Hehe. You're surely right on that! But it also doesn't sound like I'll
even be able to get a good paper or thesis out of it!

 

[Ed Prochak]

Here is some more detail:
Traversing the tree node-by-node is not allowed -- that is obviously a
recursive or iterative operation. The solution should use only the two
nodes that are presented (what I called nodes Na and Nb) to determine
if Nb is an ancestor of Na. The solution must be general - it should
work on any of the types of trees I mentioned.

The solution should be quick - ideally just a very simple/fast
computation of some type. It cannot be a search. This means the
solution cannot involve searching the tree itself, nor can it involve
search a list inside each node, for example. It should not involve any
additional storage - meaning it cannot rely upon something like an
external index (the utilization of which would effectively be a search
anyway) or extra data related to each node.

The solution should be fundamentally simple, quick and not a gimmick.

Google in comp.databases for Joe Chelko's nested sets solution for
implementing hierarchical data in a relational database. I think that
data structure will fit your need. It's in his book TREES & HIERARCHIES
IN SQL.
(so if you came up with the same solution, good bye patent.)

HTH,
Ed

 

[Willem]

Mountain wrote:
) Here is some more detail:
) Traversing the tree node-by-node is not allowed -- that is obviously a
) recursive or iterative operation. The solution should use only the two
) nodes that are presented (what I called nodes Na and Nb) to determine
) if Nb is an ancestor of Na. The solution must be general - it should
) work on any of the types of trees I mentioned.
)
) The solution should be quick - ideally just a very simple/fast
) computation of some type. It cannot be a search. This means the
) solution cannot involve searching the tree itself, nor can it involve
) search a list inside each node, for example. It should not involve any
) additional storage - meaning it cannot rely upon something like an
) external index (the utilization of which would effectively be a search
) anyway) or extra data related to each node.

How many children can a node have ?

And where did you get this problem from ?


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[wkaras]

Alf P. Steinbach wrote:
....

However, for specific cases with limited number of nodes you can do
things like that. For example, for a balanced in-memory binary tree the
path to any node can be represented as a sequence of bits. With 32-bit
memory addresses this sequence will never be 32 bits or larger (the
nodes wouldn't fit in available memory), and so a simple check of common
start sequence, just a few machine code instructions, determines
ancestorship.

....

Another limited solution is to label each leaf node with a prime
number,
and label all other nodes with the product of the labels of its
children.
The limitations are the bits of precision of the label (in the root
node, must hold p(1) * p(2) * ... * p(n), n the number of tree nodes,
p(i) the i'th prime), and that each node must have at least 2 children.

 

[=?ISO-8859-1?Q?Martin_Vejn=E1r?=]

Alf P. Steinbach wrote:
...
...

Another limited solution is to label each leaf node with a prime
number,
and label all other nodes with the product of the labels of its
children.

The limitations are the bits of precision of the label (in the root
node, must hold p(1) * p(2) * ... * p(n), n the number of tree nodes,
p(i) the i'th prime), and that each node must have at least 2 children.

A better solution might be to tag all nodes with a prime number and with
a product of all its (direct and indirect) parents. You can then check
whether (the supposed parent)'s product divides (the supposed child)'s
product.

However, with 32-bit integers, this can be implemented only for very
small trees unless you use some sort of arbitrary precision library,
which would, however, probably count as an iteration.

 

[Arthur J. O'Dwyer]

[Followups set to c.p.]

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

First, we start with a general tree (any of the trees that my data
structures book calls rooted trees or unordered trees). Then we are
given two specific nodes (Na and Nb) that belong to that tree.

We would like to know if the second node (Nb) is an ancestor of the
first node (Na).

Here's my attempt at a summary of what's been said in the various
subthreads, as much for my benefit as yours.

The problem doesn't seem terribly useful, although it is useful for
hierarchies, such as the example given in
http://www.barneyb.com/blog/archives/000570.jsp

food
/ \
meat fruit
| / \
beef apple pear

If we can solve the "is-ancestor-of" problem in O(1), then we can answer
questions such as "Is beef food?" and "Is an apple a fruit?" This could
be useful in typechecking object-oriented languages that use a lot of
subtyping and inheritance.

So, how can we implement this? Joe Celko's "nested sets" solution
looks like this:

1.food.12
/ \
2.meat.5 6.fruit.11
| / \
3.beef.4 7.apple.8 9.pear.10

Each node has two fields "left" and "right", such that
parent.left < child.left and child.right < parent.right. Then checking
that Na is a descendant of Nb simply means checking that

(Nb.left < Na.left && Na.right < Nb.right)

This solution is easy to implement, and deleting a node is easy, but
adding new nodes is naively an O(n) operation, since the "left" and
"right" fields of about half the tree's nodes need to be updated.
However, for the OO-typechecking application, lookups are going to be
much more common than inserts, so we win.
Googling "Joe Celko nested sets" does indeed turn up useful information
on this method.

Another method was proposed by Alf Steinbach in this thread: In each
node, instead of a parent pointer, store the path from the root itself,
represented as a sequence of "left" and "right" directions. For example,
the path stored in the "apple" node above would be "right,left". (Note
that this method only really works for binary trees, or with extensions,
N-ary trees. It doesn't seem applicable to general rooted trees.)
Then, checking whether Na is a descendant of Nb boils down to checking
whether Nb.path is a prefix of Na.path, which can be done in O(lg N) time
naively, and is probably possible in much less time using bitwise
arithmetic. (See below.)
As Alf points out, O(lg N) is basically O(1) on a machine with N-bit
addressing. (lg 32 is just a constant.) This means that the real-world
solution of simply storing a parent pointer in each node is basically
constant-time, too --- but the stored-path solution saves time if
dereferencing is expensive.

A third approach, which boils down to Alf's solution, is to notice that
iff Nb is an ancestor of Na, then the lowest common ancestor of Na and Nb
is Nb itself. Let's number the nodes in the order of an in-order traversal
on a complete binary tree, like this:

food.100
/ \
meat.010 fruit.110
/ / \
beef.001 apple.101 pear.111

Notice that Nx.number can also be described as "the path from the root
to Nx, followed by a 1 and right-padded with zeros." Then the paths of Na
and Nb diverge at the leftmost 1 bit of (Na.number XOR Nb.number), and
we can get their lowest common ancestor by computing

/* suppose Na = apple, Nb = fruit */
xor = Na.number ^ Nb.number; /* xor = 011 */
left = find_leftmost_one(xor); /* left = 010 */
pathmask = ~(2*left-1); /* pathmask = 100 */
path = (Na.number & pathmask) | left; /* path = 110 */

Now, since path == Nb.number, we see that indeed, Nb is the lowest common
ancestor of Na and Nb.
Unfortunately, actually /finding/ the leftmost 1 bit in a word isn't
possible in constant time using only the standard C operators. I think
Java provides a library function to do it quickly; and there is a hack
involving the FPU (convert to 'double', examine the exponent field) that
would work if you /really/ needed speed at the cost of portability.

More information on the "lowest common ancestor" algorithm is available
here: http://homepage.usask.ca/~ctl271/810/lowest_common_ancestor.pdf
The find-lowest-one FPU hack is documented here:
http://www.diku.dk/hjemmesider/ansatte/jyrki/Course/Performance-Engineering-1998/

HTH,
-Arthur

 

[Arthur J. O'Dwyer]

[Followups set to c.p.]

A better solution might be to tag all nodes with a prime number and with a
product of all its (direct and indirect) parents. You can then check whether
(the supposed parent)'s product divides (the supposed child)'s product.

The "better solution" is exactly the same as the original solution,
except that you're requiring about twice as many prime numbers since
you tag the internal nodes as well as the leaves. And that cuts down the
size of the tree by a quadratic factor at least.
Observe:

food.30
/ \
meat.2 fruit.15
| / \
beef.2 apple.3 pear.5

Only the leaf nodes need prime tags. Each internal node gets the product
of its children's tags.

However, with 32-bit integers, this can be implemented only for very small
trees

Using the original solution (using only as many primes as leaves), you
can get nine leaf nodes before overflowing the root node's 32-bit product.
Yeah, I'd say that's a very small tree. On the other hand, you can
have as many one-child internal nodes as you like, with no overhead ---
something the stored-path methods don't give you. So maybe this method
could find some highly specialized application. I'm not ruling it out.

-Arthur

 

[=?ISO-8859-1?Q?Martin_Vejn=E1r?=]

The "better solution" is exactly the same as the original solution,
except that you're requiring about twice as many prime numbers since
you tag the internal nodes as well as the leaves. And that cuts down the
size of the tree by a quadratic factor at least.

You're right, of course. For some reason, I tried to remove the "each
node must have at least 2 children" limitation, while there was none. My
bad

 

[James Lehman]

If each node maintains a linked list of pointers to its ancestors, then a
comparison of the first least number of elements in Na and Nb would either
be the same or different. Although that requires iteration or recursion.
Another way is to come up with some kind of character string code that more
or less does the same thing. But again, a string of characters requires
iteration at some point to read it or compare it to another. There really
isn't much of anything that a computer can do without at least some
iteration.

James. )

 

[CTips]

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

First, we start with a general tree (any of the trees that my data
structures book calls rooted trees or unordered trees). Then we are
given two specific nodes (Na and Nb) that belong to that tree.

We would like to know if the second node (Nb) is an ancestor of the
first node (Na).

My question to the group is this:

If there was an algorithm for answering this question _without_
traversing the tree or doing any type of search or any
iterative/recursive operations, how important and useful would that be?
Obviously, it would save a lot of computing time.

Is there a known solution that does this? Or is there a proof that it
cannot be done?

Are there any citations I should be looking at? Any help is appreciated.

Use DFS pre and post order numbers. IIRC, Na is an ancestor of Nb iff
pre(Na) < pre(Nb) and post(Na) > post(Nb). It should be in any
data-structures book.

 

[wkaras]

You're right, of course. For some reason, I tried to remove the "each
node must have at least 2 children" limitation, while there was none. My
bad

Strictly speaking, you can't get rid of this limitation so easily. If
the two
nodes that you have to determine ancestry for have the same label,
you'd
have to do some iteration (potentially) to determine who is who's
ancestor.

A slightly better solution is to give each leaf a unique mask of one
bit,
with the parent mask being or'ed together from its children. Still
need
2 children per parent min., but now you can have 32 leaves.

 

[Googmeister]

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

First, we start with a general tree (any of the trees that my data
structures book calls rooted trees or unordered trees). Then we are
given two specific nodes (Na and Nb) that belong to that tree.

We would like to know if the second node (Nb) is an ancestor of the
first node (Na).

My question to the group is this:

If there was an algorithm for answering this question _without_
traversing the tree or doing any type of search or any
iterative/recursive operations, how important and useful would that be?
Obviously, it would save a lot of computing time.

Is there a known solution that does this? Or is there a proof that it
cannot be done?

Are there any citations I should be looking at? Any help is appreciated.

Not sure I fully understand your problem, but it sounds
like it could be a special case of "least common ancestor,"
If you're willing to do a linear amount of preprocessing,
you can any answer LCA query in constant time. This
is a famous result of Harel and Tarjan from the 1980s.

 

[Chris Uppal]

I would like opinions on whether this solution could be important and
whether anyone knows if it is already solved. (I would also like to
know if anyone thinks it cannot be solved.)

If I understand you correctly then one fairly important application (in
the sense that it affects execution time enough for several papers to
have been written and published) is fast runtime sub-type checking in
object-oriented languages.

Given an object, you have it's class immediately, but knowing whether
that class is a subclass of an arbitrary other one is not automatically
O(1).

Google for
fast subtype checking

-- chris