Tree traversal - starting at leaves with only parent pointers?

7
votes

Is it conceptually possible to have a tree where you traverse it by starting at a given leaf node (rather than the root node) and use parent pointers to get to the root?

I ask this since I saw someone implement a tree and they used an array to hold all of the leaf nodes/external nodes and each of the leaf/external nodes point only to their parent nodes and those parent point to their parent node etc. until you get to the root node which has no parents. Their implementation thus would require you to start at one of the leaves to get to anywhere in the tree and you would cannot go "down" the tree since her tree nodes do not have any children pointers, only parent pointers.

I found this implementation interesting since I haven't seen anything like it but I was curious if it could still be considered it a "tree". I have never seen a tree where you start traversal at the leaves, instead of root. I have also never seen a tree where the tree nodes only have parent pointers and no children pointers.

2
data-structurestreeabstract-data-type
You've basically answered your own question. Yes, its perfectly okay to do so. Windows Presentation Foundation is a good example of why you want to do this; namely relative data binding; i.e. traverse up the tree until you find something, then bind to it. See: stackoverflow.com/questions/84278/… A more interesting question is why you want to, and why you'd only ever want parent links. – Meirion Hughes

2 Answers

4
votes

Yep, this structure exists. It's often called a spaghetti stack.

Spaghetti stacks are useful for representing the "is a part of" relation. For example, if you want to represent a class hierarchy in a way that makes upcasting efficient, then you might represent the class hierarchy as a spaghetti stack in which the node for each type stores a pointer to its parent type. That way, it's easy to find whether an upcast is valid by just walking upward from the node.

They're also often used in compilers to track scoping information. Each node represents one scope in the program, and each node has a pointer to the node representing the scope one level above it.

Hope this helps!

0
votes

If an array A of leaf nodes are given, traversal is possible. If only a single leaf node is given, I don't know how to traverse the tree. Pseudocode: 

// initial step 
add all nodes in A to a queue Q  

//removeNode(Q) returns pointer to node at front of Q 
while((node = removeNode(Q)) != NULL) 
    /* do your operation on node */ 
    add node->parent to Q