Is there a query or algorithm that will enable me to find the left and right contours for general hierarchical trees and subtrees described using the nested sets model?

I have described tree structures using nested sets. Description is basically node, lft, rgt, where node is the node in the tree, lft and rgt give the bounds of the set. Most queries then rely on the bounds or a self join on the tree table (as described by Joe Celko's Trees and Hierarchies in SQL for Smarties).

I am seeking a set based solution to retrieve left and right contours of trees. The left contour of a node is the path from and including the node to the minimum lft valued node at each level below the node. The right contour is to the maximum rgt valued node at each level below.

I can find all subordinates of a node; the path between two specified nodes; the parents of a node; and similar, but I have not been able to determine a solution to this specific need.

My use case is that I am trying to automate some aspects of laying out tree diagrams. The trees may be very large (130000 potential nodes) but very sparse (most leafs are immediate children of the root). The trees may be selectively pruned to remove the sparse elements. The algorithm I am using requires, as one step, the use of left and right contours for conflict resolution within the layout.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.