In a generic tree structure with parent and child pointers, is it possible to traverse leaf nodes without traversing the full tree? For example by starting from the left most leaf node. The idea being to optimize on deep trees.
2
votes
2 Answers
2
votes
If you represent the tree in the common c++ pointer way with a root pointing to children, there is no way to achieve this as a tree is an acyclic graph.
If you represent the tree in different ways (say as a heap using an array), you can traverse only the children as they are at an offset in the array.
Note that the leaves of a balanced binary tree comprise half the size of the tree, so there is no gain in complexity by traversing only the leaves. The fraction is a larger number for balanced ternary and other nearly-complete n-ary trees.
1
votes
No. To reach every leaf you must traverse every node.
Because a tree is acyclic, there are no redundant paths. Therefore there are no "extra" ways to get places, and therefore no shortcuts to take either. Every node is either (a) a leaf, or (b) on the critical path to one or more leaves.
The data structure would have to be enhanced in some way to optimize leaf traversal.
