CareerCup

CLR without recursion, is it right?

Predecessor - (node->left)'s->rightmost node.....

Successor - (node->right)'s ->leftmost node.....

If they exist.....:)

I thin we can directly take the left most are the right most.

According to me

following should be the algorithms for inorder successor and predecessor

predecessor(t)
{
if (left[t]!=NULL)
return the leftmost element in left[t];
if parent[t]-right==t
return parent(t)
else return parent(parent(t))

}

for successor

successor[t]
if right[t]!=NULL
return leftmost element in right[t]

if (t==parent(t)->right)
return parent(parent(t));
else return parent(t)

I don't think the previous solution works. For predecessor(t), node t could still be less than the parent's parent (and I think there was a typo: you want the right-most element of t-> left)

The problem does not describe how the BTree handles equal values (are they inked on the same node? Are they left? Are they right?) and how to consider them if they do exist (are they predecessors? Successors? Neither?)

Assuming that equal nodes, if they exist, are considered neither successors nor predecessors, I suggest:

Predecessor(t) {
    if (!t)
       return null or throw exception;
    iterator i;
    if t->left {
        i = t->left;
        while (i->left and i == t) // skip any equal nodes if applicable
            i = i->left;
        while i->right   // find the rightmost element of t->left
            i = i->right;
        return i;
    }
    i = t;
    while (i->parent)
        i = i->parent;
        if i < t  // find the first ancestor that is less than t.  
                  // ie. an ancestor who's child within t's branch is to the right
            return i;
    }
    return null or throw exception; // No predecessor
        
}

For successor, just flip right/left and </>

#include <stdio.h>
#include <stdlib.h>

struct node 
{
	int data;
	struct node *left;
	struct node *right;
};

struct node *newNode(int data)
{
	struct node *node = (struct node*)malloc(sizeof(struct node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

void insert(struct node *&node, int data)
{
	if(node == NULL)
	{
		node = newNode(data);
		return;
	}
	else
	{
		if(data > node->data)
		{
			insert(node->right, data);
		}
		else if(data <= node->data)
		{
			insert(node->left, data);
		}
	}

}

void Inorder(struct node *root)
{
	if(root != NULL)
	{
		Inorder(root->left);
		printf("%d ", root->data);
		Inorder(root->right);
	}
}

node *minimum(node *p)
{
	if(p == NULL)
		return NULL;
	while(p->left != NULL)
		p = p->left;
	return p;
}

node* maximum(node *p)
{
	if(p == NULL)
		return NULL;
	while(p->right != NULL)
		p = p->right;
	return p;
}

node *Successor(node *root, node *p)
{
	if(root == NULL || p == NULL)
		return NULL;
	if(p->right != NULL)
		return minimum(p->right);
	node *q = root;
	node *parent = q;
	if(q == p)
		return NULL;
	while(q != NULL)
	{
		parent = q;
		if((q->data < p->data) && (q != p))
			q = q->right;
		else
			break;
	}
	if(q == NULL || q != p)
		return NULL; 
	return parent;
}

node *Predecessor(node *root, node *p)
{
	if(NULL == p || NULL == root)
		return NULL;
	if(p->left != NULL)
	{
		return maximum(p->left);
	}
	node *q = root;
	node *parent = q;
	if(q == p)
		return NULL;
	while(q != NULL)
	{
		parent = q;
		if(q->data >= p->data && (q != p))
			q = q->left;
		else
			break;
	}
	if(q == NULL || q != p)
		return NULL;
	return parent;
}

node *findnode(node *root, int key)
{
	if(NULL == root)
		return NULL;
	node *p = root;
	while(p != NULL && key != p->data)
	{
		if(key <= p->data)
			p = p->left;
		else
			p = p->right;
	}

	return p;
}

<pre lang="" line="1" title="CodeMonkey32133" class="run-this">static void Successor(Node head, int num)
{
Node temp1=head, temp2=head;
int flag=3;

if(head==null)
{
return;
}

while(temp1.data!=num)
{
if(num<temp1.data)
{
temp2=temp1;
temp1=temp1.left;
flag=0;
}
else
{
temp2=temp1;
temp1=temp1.right;
flag=1;
}
}

if(temp1.right!=null)
{
temp1=temp1.right;

while(temp1.left!=null)
{
temp1=temp1.left;
}

System.out.println("INORDER successor of " + num + " is " + temp1.data);
}
else if (temp2.left == temp1)
{
System.out.println("INORDER successor of " + num + " is " + temp2.data);
flag=0;
}
else
{
Node temp3=head, temp4=head;

while(temp3.data!=num)
{
if(num<temp3.data)
{
temp4=temp3;
temp3=temp3.left;
flag=0;
}
else
{
temp3=temp3.right;
flag=1;
}
}

System.out.println("INORDER successor of " + num + " is " + temp4.data);

}

if(flag==3)
{
System.out.println("INORDER successor of " + num + " is undefined. ");

}

}</pre><pre title="CodeMonkey32133" input="yes">
</pre>

FN(cn, d)
	if(cn->d == d)
		return cn
	prev = cn
	FN(cn->l)
	SN(cn->r)

Max(n)
	if(n->r == NULL)
		return n
	Max(n->r)

Min(n)
	if(n->l == NULL)
		return n
	Min(n->l)	

P(n)
	if(n->l)
		return Max(n->l)
	else if(n->d <= r->d)	
		return prev->data
	else
		return NULL

S(n)
	if(n->r)
		return Min(n->r)
	else if(n->d > r->d)
		return NULL
	else
		return prev->data

main
	n = FN(r, d)
	p = P(n)

// InOrder Successor of a general Binary Tree. It can be even used for a BST . more optimisations // can be made for bst.
node * inOrderSuccessor(node *n)
{
// step 1 of the above algorithm
if( n->right != NULL )
return FindLeftMost(n->right);

// step 2 of the above algorithm
struct node *p = n->parent;
while(p != NULL && n == p->right)
{
n = p;
p = p->parent;
}
return p;
}

CLR should have this.