In an n-ary tree...
- Given a reference to some child node
- And a reference to a distant parent of the referenced child node
- Is there a method that a parent node can use to figure out which of its children is closest to the referenced child node and has a big-oh that's less than O(number of edges between parent and child)
Picture to illustrate my question:
A | | B / \ / \ C D <-- distant parent /|\ / | \ E F G <-- which child? /| |\ \ / | | \ \ H I J K L / /| /|\ / / | / | \ M N O P Q R ^ | | | That child node S
Things I've tried:
Iterating up the tree (O(n)), from "that child node" until the parent is found, and returning the previously visited node. This is when I noticed that my program spent too much time iterating up the tree, and could use some kind of improvement.
Have each node save a reference to every single parent it had in an array, and the index used is the number of edges between the node in the array, and the root node.
Example: "that child node" will have an array of size 5, and its immediate parent would be at index 4, and the root, index 0.
Advantage: this makes finding the node to return very quick (O(1)) because, the level (number of edges between the node, and the root node) + 1 of the parent node, will give me the index in the array in "that child node" of the node that I want to return.
Disadvantage: adding nodes to the tree becomes very expensive in memory, and computational time especially if the node is very far from the root node. expensive in memory, because it will have a huge array, and computational time because the array needs to be populated, weather it be populated by tree traversal, or copying the array from it's parent, it can take a while...
Like above, except, instead of saving references to every node, it saves log2(level) node references to nodes, in a log2() like way
Example: a node at level 1000000 would have 20 references to parent nodes. these references would be to a parent at each of the following levels: 500000, 750000, 875000, 937500, 968750 ... 999999.
Advanage: finds the node to return in O(log2(n)) to O(n), not as fast as solution above, but fast enough. much more memory efficient than above solution, but still pretty bad.
Disadvantage: still quite expensive to add new nodes to the tree in computational time, but not that bad.
I can think of variations of the above 3rd method to make things slightly more memory efficient, and time efficient, but I'm wondering if there is a method that takes O(1) time to find the solution to this problem that I am not seeing ... something like the binary search tree property, but for an n-ary tree.
The binary search tree property is desirable, because given a child node, the parent can make a step towards it, regardless of the number of edges between the given child node, and the parent.
I don't mind putting an extra index or ID or whatever data into the child node to make the method possible.