CareerCup

return inorder successor of node with value X

//pseudo-code, given an input param of X :
1. Start traversing thru the tree
2. Chk. if X=< 0, if not return 0
3. Chk. if X < Parent, if not return 0
4. Chk. if Node has children, if not return 0
5.1. Chk. If Node.right < X => return predecessor
5.2. Chk. If Node.left < X => return predecessor
6. //fall thru if neither 5.1 || 5.2 ,
Continue at step 4. and loop until done

first find the node with value x
then just find the inorder successor of that node :)
code :
int nextgreater(int x,struct node *r)
{
struct node *temp=r;
if(!r)
{
printf("not exist");
return -1;
}
while(temp!=NULL)
{
if(temp->value==x)
break;
if(x>temp->value)
temp=temp->right;
else
temp=temp->left;}
if(temp==NULL)
{
printf("NOT exist");
return -1;
}
if(temp->right)
{
temp=temp->right;
while(temp->left)
temp=temp->left;}
}
else
{
temp=r;
succ=NULL;
while(temp)
{
if(temp->value>x)
{
succ=temp;
temp=temp->left;
}
if(temp->value==x)
break;
if(temp-value<x)
{
temp=temp->right;
}
}
return succ;
}
return temp;
}

I think the 2nd post provides best answer for the
most general case. The problem definition does not
specify that the BST contains a value = X. Furthermore
it is not given what the structure of the tree is, I.e. number of child nodes (left,right). Also one has to
validate x for any possible values, nulls & 0.

Good point (that was not explicitly noted in my response). That covers "...value immediately greater than X.", and makes the rules (process of traversing the nodes) not trivial.

In Ruby:

# Given a binary search tree and a value X, find the node with value
# immediately greater than X.

class Node
  attr_accessor :value, :left, :right

  def initialize(value=nil, left=nil, right=nil)
    @value = value
    @left  = left
    @right = right
  end
end

def find_minimum(root_node)
  return root_node if root_node.left == nil
  find_minimum(root_node.left)
end

def find_pesky_sibling(root_node, value, parents=[])
  # If we can't find the value, return nil
  if root_node == nil
    return nil
  elsif value == root_node.value
    # If we don't have a right node, return the greater parent
    if root_node.right == nil
      parents.each do |parent|
        if parent.value > value
          return parent
        end
      end
      return nil
    # Otherwise, return the minimum value in the right sub-tree
    else
      return find_minimum(root_node.right)
    end
  # If our value is less than the current node, check the left sub-tree
  elsif value < root_node.value
    find_pesky_sibling(root_node.left, value, parents << root_node)
  # If our value is more than the current node, check the right sub-tree
  else
    find_pesky_sibling(root_node.right, value, parents << root_node)
  end
end

# Build example binary tree
#         10
#       /    \
#      7     15
#    /  \   /  \
#   4    9 11  20
#       /
#      8

n8 = Node.new(8)
n9 = Node.new(9, n8, nil)
n4 = Node.new(4)
n7 = Node.new(7, n4, n9)
n20 = Node.new(20)
n11 = Node.new(11)
n15 = Node.new(15, n11, n20)
root_node = n10 = Node.new(10, n7, n15)

# Find solution
puts find_pesky_sibling(root_node, 9).inspect

without using parent pointer

n: node whose successor needs to be found
FM(): Find min val in a tree
rt: root
s: successor
S(r, n)
	if(n->r)
		return FM(n->r)
	else
		while(rt)
			if(n->d < r->d)
				s = rt->d
				rt = rt->l
			if(n->d > r->d)
				rt = rt->r
			else
				break
		return s