Thursday, January 5, 2012

Find Depth of a binary tree

int BSTree::getDepth(Node* node)
{
if(!node)
return 0;

int ld = getDepth(node->left);
int rd = getDepth(node->right);

return MAX(ld, rd) + 1;
}

Tuesday, January 3, 2012

Google Question: Find nth minimum in Binary Search Tree.

1. Without extra field in Node structure --

Do inorder traversal and count number of node visited. When count is equal to n return the node.
void BSTree::findNthElem(Node* node, int& n, int& retval)
{
if(!node && n)
retval = -1;
else if(n)
{
findNthElem(node->left, n, retval);
if(n)
{
n = n - 1;
if(n == 0)
retval = node->data;
findNthElem(node->right, n, retval);
}
}
}