Quad tree

[Geeksoftie]

Quad Tree is a tree with four pointers like North East, North West, South East and South West. Its used a lot in region query. Is there a way where I can find the min and max nodes a quad tree using some trick or is there some standard formula to find that out ?

[WaltP]

find the min and max nodes a quad tree

Are you missing a verb or something??

[L7Sqr]

The simple solution is a recursive one. In pseducode that would look like:

int quad_max(root) {
   if (root.is_a_leaf) {
      return root.value
   } else {
      return max(
         quad_max(root.east),
         quad_max(root.south),
         quad_max(root.west),
         quad_max(root.north))
   }
}

Although, to be efficient you would probably want to implement a caching scheme to that search to prevent having to search every node each time you call quad_max.

[mrnutty]

Although, to be efficient you would probably want to implement a caching scheme to that search to prevent having to search every node each time you call quad_max.

Or if its needed frequently, just have a variable to keep track of current max/min

[L7Sqr]

@firstPerson:
I'd actually argue that it would be te responsibility of the structure to maintain that. Otherwise you'd be keeping redundant state. The algorithm would only need to look at the topmost root to get the cached value - which is basically constant time.