Friday, May 24, 2013

Microsoft Question: Find balanced binary sub-tree of size N within a binary tree


void BinaryTree::findBalancedTree(Node* node, int& height, int& size, int N, Node*& out)
{
if(!node)
{
size =0;
height = 0;
return;
}
int lheight = 0, rheight = 0, lsize = 0, rsize = 0;
findBalancedTree(node->left, lheight, lsize, N, out);
findBalancedTree(node->right, rheight, rsize, N, out);

if(abs(lheight - rheight) <= 1 && lsize + rsize + 1 == N)
{
out = node;
}

height = max(lheight, rheight) + 1;
size = lsize + rsize + 1;
}

No comments:

Post a Comment