Thursday, January 10, 2008

Max Heap + Binary Search Tree

A rooted binary tree with keys in its nodes has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key. It has the heap property if, for every node, the keys of its children are all smaller than its own key.
You are given a set of n binary tree nodes that each contain an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property. If you pay attention only to the second key in each node, the tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a binary search tree.Describe a recursive algorithm for assembling such a tree


Solution:
Lets assume that the tree node has two keys K1 and K2.
K1 satisfies the BST property
K2 satisfies the Max Heap Property.

Our problem is to build a binary tree which satisfies both the properties.
For a maximal heap the root node must be the maximum.
So we find the node which has the K2 max. And make it as the root node.
Among the remaining nodes, The nodes to the left of the tree will be those whose K1 value is less than that of the Root nodes K1. And rest will be on the right side of the root. Now again repeat the procedure for finding the next left node of root and right node of root using the same logic above.

4 comments:

Anonymous said...

I would suggest . Create a BST first . then then do tree rotations as to get the Heap property !!

Anonymous said...

I think its better to get a BST first and then do tree rotations to get Heap !!

Losing All Hope is Freedom said...

I think its better to get a BST first and then do tree rotations to get Heap !!

Losing All Hope is Freedom said...

I think its better to get a BST first and then do tree rotations to get Heap !!