Parent pointer tree

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an in-tree or parent pointer tree is an N-ary <a href="/facts/Tree_data_structure/RcXz9noF">tree data structure</a> in which each node has a <a href="/facts/Pointer_(computer_programming)/fPoNzy9b">pointer</a> to its <a href="/facts/Parent_node/RcXz9noF">parent node</a>, but no pointers to <a href="/facts/Child_node/RcXz9noF">child nodes</a>. When used to implement a set of <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stacks</a>, the structure is called a spaghetti stack, cactus stack or saguaro stack (after the <a href="/facts/Saguaro/d8CmXlzl">saguaro</a>, a kind of cactus). Parent pointer trees are also used as <a href="/facts/Disjoint-set_data_structure/QnFQNedE">disjoint-set data structures</a>.
</p><p>The structure can be regarded as a set of <a href="/facts/Singly_linked_list/Ik4JTgJW">singly linked lists</a> that share part of their structure, in particular, their tails. From any node, one can traverse to ancestors of the node, but not to any other node.
</p>

Parent pointer tree open-in-new

Parent pointer tree