CareerCup

#define MAX(x,y) ((x > y) ? x:y)
int height(struct node *root)
{

if(root == null)
return 0;
ldepth = height(root->left) + 1;
rdepth = height(root->right) + 1;

return MAX(ldepth, rdepth);
}

int maxDepth(struct node * node){
	if(node==NULL)
		return(0);
	else {
		int ldepth=maxDepth(node->left);
		int rdepth=maxDepth(node->right);
		if(ldepth>rdepth)
			return(ldepth+1);
		else
			return(rdepth+1);
	}
}

but where is the usage of binary search tree property
this is like the solution for binary tree

In this problem, we are not required to use the searching property of the BST (left <= right), since we are not concerned about that when finding the depth. So, then it remains a binary tree only.

int btree::minheight(btreenode *k,queue q1,queue q2)
{
int h = -1;
q1.enqueue(k);
while(q1.front != -1)
{
btreenode* temp;
while(q1.front != -1)
q2.enqueue(q1.dequeue());
h++;
while(q2.front != -1)
{
temp = q2.dequeue();
if(temp -> leftchild != NULL)
{
q1.enqueue(temp -> leftchild);
}
else
{
cout << "Min height = " << h << endl;
system("pause");
exit(0);
}
if(temp -> rightchild != NULL)
{
q1.enqueue(temp -> rightchild);
}
else
{
cout << "Min height = " << h << endl;
system("pause");
exit(0);
}
}
}
return h;
}

Recursive approach:

int depthTree(Tree t) {
if(t==null || t.left==null || t.right==null)

}

Recursive approach:

int depthTree(Tree t) {
if(t==null || t.left==null || t.right==null)
return 0;
return(MAX(1+depthTree(t.left) , 1+depthTree(t.right));
}

can take advantage of BST by using heuristic DFS with pruning

Clue: create two string of preorder and inorder and apply some logic

can you utilize the sorted BST behavior?

public int maxDepth(Node root)
{
if (root == null) { return 0; }

return 1 + Math.Max(maxDepth(root.leftNode), maxDepth(root.rightNode));
}