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 On Dec 15, 2:07 pm, snehal jain <[email protected]> wrote: > 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 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
