Google Interview Question Software Engineer / Developers
O(n) solution is provided.
This solution uses the O(log(n)) space in the stack,
and I am not sure whether this will violate the requirements.
The key concept is that, while visiting each node,
we separate the node from heap and add it to BST
with maintaining the structure.
In doing so, we keep following invariant:
the current node is always the leftmost node of the heap
or the top element.
For this, we might need to modify the left pointer of
the parent IN HEAP temporarily and recover it appropriately.
The procedures are:
1. visit left child recursively
2. swap top elements with the cur node
3. detach cur node from heap and add it to BST
4. visit right child recursively
For step 3 separation, there are two cases.
(1) case 1. node is not the top element
: it is guaranteed that we are left children of
the parent IN HEAP.
so change the left pointer of the parent to the right child.
(2) case 2. node is the top element
: make the right child as a top element of the heap
Following is c++ implementation.
Node *heapToBST(Node *cur, Node *parent, Node **heapRef)
{
// 1. visit left child
if(cur->left){
// left pointer of myself can be modified
// for maintaining heap in case 1 of step 3.
// so it should be recovered from return value
cur->left = heapToBST(cur->left, cur, heapRef);
}
// 2. swap top elements with cur node
swap(cur->data, (*heapRef)->data);
// 3. detach cur node from heap
if(parent){
// case1. we are not the top element
// cur == parent->left by the invariant
parent->left = cur->right;
// heapify the heap again
heapify(*heapRef);
}
else {
// cur node is top element i.e., cur == head
*heapRef = (*heapRef)->right;
}
// 4. visit right child
if(cur->right){
heapToBST(cur->right, parent, heapRef);
}
return cur;
}
This is the test result
[Mean Heap]
0
1 2
3 4 5
6 7 8
9
[BST]
3
2 8
0 5 9
1 4 6
7
Convert( Node)
{
if(Node!=null)
{
Convert(Node->left)
Convert(Node->right)
Fix(Node)
}
}
Fix(Node)
{
if(Node!=null)
{
if(Node->left!=null && Node->right!=null)
if(Node->left->value < Node->right->value)
{swap(Node->left, Node); Fix(Node->left);
else
{
Node->left to Node->right, Node->right to Node, Node to Node->left
Fix(Node->left);Fix(Node->right)
}
}
}
T(N) = 2T(N/2) + O(logN) (Fix(Node) is O(logN) ),by Master theorem，T(N) = O(N)
First, confirm that they mean a binary min heap.
In a binary min heap, all the right (greater than) pointers are correct, so we just need to swap the left pointers, and bubble the left-most pointers up as the new roots:
swapLeft (node, parent)
{
.
. if node.right
. node.right = keepRight(node.right)
.
. leftHolder = node.left
. node.left = parent
.
. if leftHolder
. newRoot = swapLeft(leftHolder, node)
. else
. newRoot = node
.
. return newRoot
}
keepRight (node)
{
. if node.right
. node.right = keepRight(node.right)
.
. if node.left
. newRoot = swapleft(node.left, node)
. else
. newRoot = node
.
. return newRoot
}
root = swapLeft(root, null)
Here is my code.
It converts (in-place) a min heap {1, 4, 2, 5, 6, 7, 3} to a correct BST {4, 2, 6, 1, 3, 5, 7}.
The basic idea is as follows:
1) Do the in-order traverse of the tree.
2) When visiting a node
2-1) extract min value from the heap
2-2) add value of the current node into the min heap
2-3) put the min value to the current node
This way, we are gradually converting the min heap into BST.
static int prevMin = Integer.MIN_VALUE;
static void minHeapToBST(int[] arr) {
inorderTraverse(arr, 0);
}
static void inorderTraverse(int[] arr, int node) {
int left = node * 2 + 1;
int right = node * 2 + 2;
if (left < arr.length) {
inorderTraverse(arr, left);
}
// remove min from the heap
int min = removeMin(arr, 0, prevMin);
prevMin = min;
// put current node's value into the heap
arr[arr.length - 1] = arr[node];
bubbleUp(arr, arr.length - 1);
// put the extracted min value to the current node
arr[node] = min;
if (right < arr.length) {
inorderTraverse(arr, right);
}
}
// min is to prevent removing values that are now part of BST.
static int removeMin(int[] arr, int root, int min) {
// normal min heap operation
if (arr[root] > min) {
int temp = arr[root];
arr[root] = arr[arr.length - 1];
sinkDown(arr, root, min);
return temp;
} else {
// if root is already part of the BST, move on to the right child
if (root * 2 + 2 < arr.length) {
return removeMin(arr, root * 2 + 2, min);
} else {
return Integer.MIN_VALUE; // cannot happen
}
}
}
static void sinkDown(int[] arr, int node, int min) {
int smallest = node;
int left = smallest * 2 + 1;
int right = smallest * 2 + 2;
if (left < arr.length && arr[left] > min && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < arr.length && arr[right] > min
&& arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest != node) {
int temp = arr[node];
arr[node] = arr[smallest];
arr[smallest] = temp;
sinkDown(arr, smallest, min);
}
}
// nothing special here.
static void bubbleUp(int[] arr, int node) {
int parent = (node - 1) / 2;
if (parent >= 0) {
if (arr[parent] > arr[node]) {
int temp = arr[parent];
arr[parent] = arr[node];
arr[node] = temp;
bubbleUp(arr, parent);
}
}
}
Here is my code.
It converts (in-place) a min heap {1, 4, 2, 5, 6, 7, 3} to a correct BST {4, 2, 6, 1, 3, 5, 7}.
The basic idea is as follows:
1) Do the in-order traverse of the tree.
2) When visiting a node
2-1) extract min value from the heap
2-2) add value of the current node into the min heap
2-3) put the min value to the current node
This way, we are gradually converting the min heap into BST.
static int prevMin = Integer.MIN_VALUE;
static void minHeapToBST(int[] arr) {
inorderTraverse(arr, 0);
}
static void inorderTraverse(int[] arr, int node) {
int left = node * 2 + 1;
int right = node * 2 + 2;
if (left < arr.length) {
inorderTraverse(arr, left);
}
// remove min from the heap
int min = removeMin(arr, 0, prevMin);
prevMin = min;
// put current node's value into the heap
arr[arr.length - 1] = arr[node];
bubbleUp(arr, arr.length - 1);
// put the extracted min value to the current node
arr[node] = min;
if (right < arr.length) {
inorderTraverse(arr, right);
}
}
// min is to prevent removing values that are now part of BST.
static int removeMin(int[] arr, int root, int min) {
// normal min heap operation
if (arr[root] > min) {
int temp = arr[root];
arr[root] = arr[arr.length - 1];
sinkDown(arr, root, min);
return temp;
} else {
// if root is already part of the BST, move on to the right child
if (root * 2 + 2 < arr.length) {
return removeMin(arr, root * 2 + 2, min);
} else {
return Integer.MIN_VALUE; // cannot happen
}
}
}
static void sinkDown(int[] arr, int node, int min) {
int smallest = node;
int left = smallest * 2 + 1;
int right = smallest * 2 + 2;
if (left < arr.length && arr[left] > min && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < arr.length && arr[right] > min
&& arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest != node) {
int temp = arr[node];
arr[node] = arr[smallest];
arr[smallest] = temp;
sinkDown(arr, smallest, min);
}
}
// nothing special here.
static void bubbleUp(int[] arr, int node) {
int parent = (node - 1) / 2;
if (parent >= 0) {
if (arr[parent] > arr[node]) {
int temp = arr[parent];
arr[parent] = arr[node];
arr[node] = temp;
bubbleUp(arr, parent);
}
}
}
Take 3 nodes at a time in the tree (parent and its 2 children)
Now rearrange the values such that left is the min , parent is the middle element and right is the highest of the three. Do it for every node in the tree
We can do it by traversing the tree and swaping the values as many times as the hight of tree. Tree traversal will always take extra space (stack for recursive calls). Below is the psudo code:
MinHeapToBst (Root){
if (Root){
TempRoot = Root;
LeftChild = Root->LeftChild;
RightChild = Root->RightChild;
MinHeaptoBst (LeftChild);
MinHeaptoBst (RightChild);
if (RightChild && LeftChild){
if (LeftChild->Key > RightChild->Key){
SWAP (LeftChild->Key, RightChild->Key);
}
SWAP (LeftChild->Key, Root->Key);
}
else if (LeftChild){
SWAP (LeftChild->Key, Root->Key)
}
}
}
1. N<-Number of node in tree, H<-log(N), hight of tree, R<-Root of tree;
2. While (H > 0){
MinHeapToBst (R);
}
Running time is Nlog(N)
Anybody, please let me know if it can be done witout using stack (extra space).
Sorry for the mistake, the psudo code is as below:
MinHeapToBst (Root){
. if (Root){
. TempRoot = Root;
. LeftChild = TempRoot->LeftChild;
. RightChild = TempRoot->RightChild;
. MinHeaptoBst (LeftChild);
. MinHeaptoBst (RightChild);
. if (RightChild && LeftChild){
. if (LeftChild->Key > RightChild->Key){
. SWAP (LeftChild->Key, RightChild->Key);
. }
. SWAP (LeftChild->Key, TempRoot->Key);
. }
. else if (LeftChild){
. SWAP (LeftChild->Key, TempRoot->Key)
. }
. }
}
1. N<-Number of node in tree, H<-log(N), hight of tree, R<-Root of tree;
2. While (H > 0){
. MinHeapToBst (R);
. H <- H-1;
. }
lyle.smu.edu/~saad/courses/cse3358/ps7/problemset7sol.pdf
- swk October 22, 2010problem 4 (b)