int BSTree::getDepth(Node* node)

{

if(!node)

return 0;

int ld = getDepth(node->left);

int rd = getDepth(node->right);

return MAX(ld, rd) + 1;

}

## Thursday, January 5, 2012

## 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);

}

}

}

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);

}

}

}

Subscribe to:
Posts (Atom)