435,640 Members | 2,279 Online
Need help? Post your question and get tips & solutions from a community of 435,640 IT Pros & Developers. It's quick & easy.

# Would this solution be important? Is it already solved?

 P: n/a 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. Apr 24 '06 #1
19 Replies

 P: n/a 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 Apr 24 '06 #2

 P: n/a 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. 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. Apr 24 '06 #3

 P: n/a * 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. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Apr 24 '06 #4

 P: n/a 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. 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 Apr 24 '06 #5

 P: n/a 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. Apr 24 '06 #6

 P: n/a 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 ;) Apr 24 '06 #7

 P: n/a >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! :( Apr 24 '06 #8

 P: n/a 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. 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 Apr 24 '06 #9

 P: n/a 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 Apr 24 '06 #10

 P: n/a 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. Apr 24 '06 #11

 P: n/a wk****@yahoo.com wrote: 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. 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. -- Martin Apr 24 '06 #13

 P: n/a [Followups set to c.p.] On Mon, 24 Apr 2006, [ISO-8859-1] Martin Vejnár wrote: wk****@yahoo.com wrote: 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. 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 Apr 24 '06 #14

 P: n/a Arthur J. O'Dwyer wrote: Martin Vejnár wrote: wk****@yahoo.com 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. 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 :) -- Martin Apr 24 '06 #15

 P: n/a 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. :o) "Mountain" wrote in message news:11**********************@g10g2000cwb.googlegr oups.com... 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. Apr 24 '06 #16

 P: n/a 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. 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. Apr 24 '06 #17

 P: n/a Martin Vejnár wrote: Arthur J. O'Dwyer wrote: Martin Vejnár wrote: wk****@yahoo.com 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. 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 :) 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. Apr 25 '06 #18

 P: n/a 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. 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. Apr 25 '06 #19

 P: n/a 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.) 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 Apr 25 '06 #20

### This discussion thread is closed

Replies have been disabled for this discussion.