CareerCup

Here was my solution:

public class Node
{
public Node left;
public Node right;
public Node parent;
public int value

public static Node findNext(Node n)
{

Node parent p=n.parent
if(parent == null)
return findNode(parent.left);

if(n==parent.left && parent.right == null)
return parent;
else if(n==parent.right && parent.right != null))
return findNode(parent.right);
}
}

int Find(struct Node *node)
{
if(!node)
return -1;
int res=-1;
struct Node *temp=NULL;
if(node->right)
{
temp=node->right;
while(temp->left)
temp=temp->left;
res=temp->data;
}
else
{
struct Node *parent=node->parent;
temp=node;
while(parent && temp==parent->right)
{
temp=temp->parent;
parent=parent->parent;
}
if(parent)
res=parent->data;
}
return res;
}

Node* InorderSuc(Node* fS){
	if(!fS)
		return NULL;
	if(!fS->right && fS->Parent->left==fS) 
		return fS->Parent;
	if(fS->right && fS->Parent->right==fS){
		Node *succ=fS->right;
		while(succ->left)
			succ=succ->left;
		return succ;
	}
	return NULL;
}

The tree doesn't look good. Here it is again

root: 7, left 5, right 11
5: left 4, right 6
4: left 2
11: left 9
9: right 15

1. Find the root node. (This has to be done since you aren't guaranteed to start at the root)
2. Traverse the tree in search of the give value.
3. Return the values parent

The question is to find the inorder successor of the given node.
1. if the node has a rigth child then it is the next node.
2. else if the parent.data is greater than the node.data then it is the next node
3. else if the parent.data is less than the node.data
a) follow the parent till it is null or its data is greater
than the node.data.
i) if a parent node is found whose data is greater then it is the next node
ii) if it is null then there is no next node hence return null

if ( node.right !=null )
	return node.right
else if ( node.parent.data > node.data )
	return node.parent
else if ( node.parent.data < node.data ) {
	temp = node.parent
	while(temp !=null &&temp.data < node.data)
		temp = node.parent
	if(temp > node.data)
		return temp
	else if(temp==null)
		 return null
        }

public static Node search(Node node, int value) {
		while (node != null && node.getValue() != value) {
			if (value > node.getValue())
				node = node.getRigth();
			else
				node = node.getLeft();
		}
		return node;
	}

	public static Node findNode(Node node, int value) {
		Node _node = node;
		if (node.getValue() != value) {
			Node current = node;
			while (current.getParent() != null) {
				current = current.getParent();
			}
			_node = search(current, value);
		}
		if (_node == null)
			return null;
		
		if (_node.getRigth() != null) {
			return min(_node.getRigth());
		} else {
			Node current = _node;
			Node parent = current.getParent();
			while (parent != null && parent.getRigth() == current) {
				current = parent;
				parent = parent.getParent();
			}
			return parent;
		}
	}

	public static Node min(Node node) {
		if (node == null)
			return null;
		Node cur = node;
		while (cur.getLeft() != null)
			cur = cur.getLeft();
		return cur;
	}

O(log(n)) complexity.

public Node next(){
		if(right != null){
			return right.min();
		} else {
			Node next = parent;
			while(next != null && next.value < value){
				next = next.parent;
			}
			
			return next;
		}
	}

class TreeNode {
    int val;
    TreeNode leftchild;
    TreeNode rightchild;
    TreeNode parent;

    public TreeNode(int val) {
	this.val = val;
	leftchild = null;
	rightchild = null;
	parent = null;
    }
}

public class Solution {

    public static TreeNode findNode(TreeNode n) {
	if (n == null) {
	    return null;
	}
	// root node
	if (n.parent == null) {
	    return findLeftMost(n.rightchild);
	}
	// right child not null
	if (n.rightchild != null) {
	    return findLeftMost(n.rightchild);
	}
	// right child is null, find next upper level
	// n is leftchild
	if (n.parent.leftchild == n) {
	    return n.parent;
	}
	// n is rightchild, which means n.parent has been fully checked
	if (n.parent.rightchild == n) {
	    return findNode(n.parent.parent);
	}
    }
    
    public static TreeNode findLeftMost(TreeNode root) {
	if (root == null) {
	    return null;
	}
	while (root.leftchild != null) {
	    root = root.leftchild;
	}
	return root;
    }
}

if the node has a right subtree, then the next element will be left most node in subtree
	else if the node is the left child of the parent, parent is the next node
	else if the node is the right child of the parent, find the first grandparent, to whose left, this node fall
	else NULL

here is the solution I believe

1. first find the ultimate parent. ( while (tmp.getParent() !=null) node.getParent; )
2. Once you have ultimate parent , traverse the tree in inorder algo and get the next element, which would be desired node.

O(1) solution:

if node.right return min(node.right.value, node.parent.value); else return node.parent.value;