CareerCup

find the closest parent with given node in left subtree
keep track of distance from this parent to given node
search the parent's right subtree for the first child that matches the distance
if no child of the correct distance is found with this parent, re-iterate by finding the next closest parent


pseudo code below

right_neighbor = Null
node = given_node
distance = 0

while(True):
	# find closest parent with given node in its "left subtree"
        # return parent and distance from parent to node
	(parent, distance) = find_left_subtree_parent(NODE = node, start_distance = distance)

        if (parent == Null)
	{    return Null } ## reached root without finding right neighbor
	else
        { right_neighbor = find_child_in_right_subtree(parent, distance) }

        if(right_neighbor != Null)
        {   return right_neighbor; }
	else
	{	## the closest parent did not have the right neighbor
                ## keep traversing up to find next parent with given node in left subtree
		node = parent
	}

what is immediate right neighbor? Do you mean inorder successor?

struct tree_node* righ_neighbour(struct tree_node* node, int i)
{
if(node == NULL)
return NULL;

int j;
struct tree_node* cur = node;
for (j = 0; j < i && cur != NULL; j++) {
cur = cur->children[0];
}

if(cur != NULL)
return cur;
return right_neighbour(node->parent, i+1);
}

call it like right_neighbour(node->parent, 1)

struct Node
  {
      int data;
      Node* left;
      Node* right;
      Node* parent;
  };

Node* RightNeighbor(Node* node)
  {
      if(!node)
        return node;
      uint level  = 1;
      Node* currParent = node->parent;
      while(currParent)
      {
          Node* temp = GetLeftMostChild(currParent->right, level-1);
          if(temp)
            return temp;
          ++level;
          currParent = currParent->currParent->parent;
      }

      return null;
  }

Node* GetLeftMostChild(Node* node, uint level)
  {
      if(0 == level)
          return node;
      if(node->left)
          return GetLeftMostChild(node->left, level-1);
      if(node->right)
          return GetLeftMostChild(node->right, level-1);

       return null;
  }

struct node* find_right_neighbour_util(struct node* which_node,struct node* prev,int level){
	if(which_node == NULL){
		return NULL;
	}
	if(prev == NULL){
		prev = which_node;
		which_node = which_node->parent;
		return find_right_neighbour_util(which_node, prev, level+1);
	}
	if(level == 0){
		return which_node;
	}
	if(prev->parent == which_node){
		if(prev == which_node->left && which_node->right){
			prev = which_node;
			which_node = which_node->right;
			return find_right_neighbour_util(which_node, prev, level-1);
		}
		else{
			prev = which_node;
			which_node = which_node->parent;
			return find_right_neighbour_util(which_node, prev, level+1);
		}
	}

	struct node* left = find_right_neighbour_util(which_node->left, which_node, level-1);
	if(left)
		return left;
	struct node* right = find_right_neighbour_util(which_node->right, which_node, level-1);
		return right;
	}

struct node* find_right_neighbour(struct node* which_node){
	struct node* prev, *result;
	int level = 0;
	prev = NULL;
	result = find_right_neighbour_util(which_node, prev, level);
	return result;
}

int printRightMostNeighbor(struct bst *b) //i.e., neighbor in level-order sense without using level-order or bfs
{
	int level1=0;
	int level2=0;
	if(b==NULL || b->parent==NULL)
		return NULL;
	if(b->parent->rc!=NULL && b->parent->rc!=b)
		return b->parent->rc;
	struct bst *tmp=NULL;
	struct bst *tmp1=b;
	while(b->parent!=NULL)
	{
		tmp=b;
		b=b->parent; 
		level1++;
		if(b->rc!=NULL && b->rc!=tmp)
			break;
	}
	while(level2!=level1-1)
	{
		if(b->rc==NULL)
			return NULL;
		b=b->rc;
		level2++;
	}
	if(b->rc==tmp1)
		return NULL;
	if(b->lc!=NULL)
		return b->lc;
	else if(b->rc!=NULL)
		return b->rc;
	else
		return NULL;
}

Its time complexity is O(lg n).

public Node findRightNode(Node n) {
if (n == null)
return null;

if (n.right != null)
return leftMostChild(n.right);

Node c = n;
Node p = c.parent;
while (p != null && p.left != c) {
c = p;
p = c.parent;
}
return p;
}

public Node leftMostChid(Node n) {
if (n == null)
return null;
while (n.left != null)
n = n.left;
return n;
}

public Node findRightNode(Node n) {
	if (n == null)
		return null;
	
	if (n.right != null)
		return leftMostChild(n.right);

	Node c = n;
	Node p = c.parent;
	while (p != null && p.left != c) {
		c = p;
		p = c.parent;
	}
	return p;
}

public Node leftMostChid(Node n) {
	if (n == null)
		return null;
	while (n.left != null)
		n = n.left;
	return n;
}

public Node findNextNode(Node node){
// special base case
if(node == null || node.parent == null){
return null;
}

// base case
if(node = node.parent.left && node.parent.right != null){
return node.parent.right;
}

Node parent_Neighbor = findNextNode(node.parent);

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

parent_Neighbor = findNextNode(parent_Neighbor);
}

return null;
}

Node* RightNeighbor(Node* node) {
		
Node *par=node->parent;
if(par&&par->right&&par->left==node)
return par->right;

int level=1;
Node *res=NULL;

while(par){
bool a=rightneighbourhelper(par->right,&res,level);
if(a) 
break;
par=par->parent;
level++;
}

return res;
}
 
bool rightneighbourhelper(Node *root,Node **res,int level){

if(!root)
return false;

static int time=0;

if(level==0&&time==0){
*res=root;
time=1;
return true;
}

return rightneighbourhelper(root->left,res,level-1)||rightneighbourhelper(root->right,res,level-1);

}