KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
We are given an array of 2 m - 1 distinct, comparable elements, indexed starting from 1. We can view the array as a complete binary tree: Node is placed at index i. Left child is placed at 2i. Right child is placed at 2i+1. For instance, the array [7 6 4 5 2 3 1] is the tree 7 / \ 6 4 / \ / \ 5 2 3 1 Now when viewed as a binary tree, these elements satisfy the heap property, a node is greater than both its children: A[i] > A[2i] and A[i] > A[2i+1] Are there reasonably fast, in-place algorithm to shuffle the elements of the array around so that the resulting binary tree (as described above) is a binary search tree? Recall that in a binary search tree, a node is greater than all its left descendants, and less than all its right descendants. For instance the reshuffle of the above array would be [4 2 6 1 3 5 7] which corresponds to the binary search tree 4 / \ 2 6 / \ / \ 1 3 5 7
Tags (comma-separated)
Save Edits
Cancel