CareerCup

There is no in-order successor for the node with value 6.

there is no inorder successor

@algos interpretation of the problem is very smart. However, if this question is concern with the actual structure of the given BST, then we can use something like the code below:

struct bst* InorderSuccessor(struct bst *b, struct bst *value)
{
	if(tmp->lc!=NULL)				
		return tmp->lc;	
	else if(tmp->rc!=NULL)	
		return tmp->rc;			
	else if(tmp==tmp->parent->lc && tmp->parent->rc!=NULL)
		return tmp->parent->rc;
	else
	{		
		struct bst *tmp1=tmp->parent;						
		while(tmp1->parent!=NULL && (tmp1->rc==NULL || tmp1->rc==tmp))
		{
			tmp=tmp1;
			tmp1=tmp1->parent;				
		}
		if(tmp1->rc!=NULL)
			val=tmp1->rc;
	}
	return NULL;
}

inorder travesal always results in sorted values and there is no vlaue grt than 6 . means no successer

No in order successor to 6, and here is my solution.

public class BSTinorder
{
	// Return the in order successor of a given node in a BTS
	
	public class Node {
		public Node right;
		public Node left;
		public float data;
		public Node(float data, Node left, Node right) {
			this.right = right;
			this.left = left;
			this.data = data;
		}
	}

	private Node root = new Node(4,
			new Node(2,
				new Node(1, null, null),
				new Node(3, null, null)
				),
			new Node(6,
				new Node(6,
					new Node(5,
						new Node(4.5f, null, null),
						new Node(5.5f, null, null)
						),
					null
					),
				null
				)
			);
	
	public Node after(float value, Node node) {
		if (value >= node.data) {
			return node.right == null ? null : after(value, node.right);
		} else {
			if (node.left == null) {
				return node;
			}
			Node afterLeft = after(value, node.left);
			if (afterLeft == null) {
				return node;
			}
			return node.data < afterLeft.data ? node : afterLeft;
		}
	}
	
	public static void main(String[] args)
	{
		BSTinorder instance = new BSTinorder();		
		Node node = instance.after(Float.parseFloat(args[0]),instance.root);
		if (node == null) {			
			System.out.println("no successor");
		} else {
			System.out.println(node.data);
		}
	}
}

The logic that I would put into this question would be sth like this:

if(root)
{
InOrderSuccessor(r->left)

}

why don't we just do in order traversal of the tree and store it into an array, then we just simply find the next item after the node we are interested. If null then means it doesn't have an in order successor. time O(n), space O(n). I guess the only penalty here is the extra memory space used.

Here is the is the Inorder sequence:
1,2,3,4,4.5,5,5.5,6

In order successor in a BST will be the smallest number greater than the given number.
Which would be the left most node in its right subtree.

def in_order_successor(node):
    if node.right is None:
        return None
	temp_node = node.right
	while temp_node.left != None:
		temp_node = temp_node.left
	return temp_node

as per the sequence the possible in-order successor could be 7. if you need to find the in-order successor with the existing data then return -1 as that doesn't exist

---------------4
-------2--------------6
----1----3-------5-------7
--------------4.5--5.5
4 is average of 2&6
2 is average of 1&3
5 is average of 4.5&5.5
6 is average of 5&7