CareerCup

The run time is of the order of

int printNextElement(Node* root, int num) {

  if(!root) {
    return INT_MAX;
  }

  int l = printNextElement(root->left, num);
  int r = printNextElement(root->right, num);

  int temp = INT_MAX;
  if(num < root->data)
    temp = std::min(l, root->data);
  else
    temp = l;


  return std::min(temp, r);
}

Question is on BST.

1. i believe, next smallest element would be rightmost of left element.
if right sub tree of left element is empty then it would be left node.

Inorder predecessor will be the answer

public int nextSmall(int val) {
tree = root;
while (tree != null) {
if (tree.value == val) {
node = tree;
break;
} else if (tree.value > val) {
parent = tree;
tree = tree.left;
} else {
parent = tree;
tree = tree.right;
}
}

if (node.left != null) {
if (node.left.right != null) {
return treeMax(node.left.right).value;
} else {
return node.left.value;
}
} else {
return parent.value;
}
}

public int getNextLeastElement(Node root, int n1, int tmp) {
int secondMax=-1,l,r,rootValue;

if(root !=null) {
rootValue=root.getValue();
l=getNextLeastElement(root.getLeft(), n1, tmp);
r=getNextLeastElement(root.getRight(), n1, tmp);
// System.out.println("node is : " + root.getValue() + secondMax);

if( l < r ) {
if(r <n1){
secondMax=r;
}
}
else{
if(l <n1 ){
secondMax=l;
}
}
if(secondMax < rootValue && rootValue <n1)
secondMax=rootValue;
}
return secondMax;
}

To get the next least element of a given node , we have to find the largest element in the left sub tree of a given node. Let me know if I am wrong.

private Node findNextLeastNode(Node root) 
{
	if(root == null) {
		return null;
	}

	if(root.right != null) {
		root = root.right;
		while(root.left != null) {
			root = root.left;
		}
	}

	return root;
}