CareerCup

revinorder(struct node *node)
{
 static struct node * prev = NULL;

 if(node == NULL)
	return;

 revinorder(node->right);

 node->right = prev;
 prev = node;

 revinorder(node->left) ;
}

@Razz - Do you want to convert BST to a single threaded binary tree or do you want to change right pointer of each and every node to its inorder successor even if its right pointer is not null ?

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


void ConnectToInorderSuccessor(struct node* p)
{
static struct node *next = NULL;

if (p)
{
ConnectToInorderSuccessor(p->right);

p->next = next;

next = p;

ConnectToInorderSuccessor(p->left);
}
}

Enjoy !!

Node* inorder(Node* curr, bool isRight=false, Node* par=NULL){
	
	if(!curr)	return NULL;

	else{
		inorder(curr->left, false, curr);

		//inorderPred is the recent inorder predecessor viz. the rightmost child
		Node* inorderPred = inorder(curr->right, true, curr);
		
		//if the current node a left child
		if(!isRight){
			//if there is no right child then simply point to parent node
			if(!curr->right)		curr->right = par;

			//if there is a right child and current node is a left child
			//then inorder predecessor must point to its parent
			else if (inorderPred)		inorderPred->right = par;
		
			return curr;
		}
		
		//if the node is a right child
		else{
			//return the rightmost node as the current inorder predecessor
			if(!inorderPred)	return curr;

			else return inorderPred;
		}
	}
}

using stack u can do it easily !!

Here is the algo :


Step-1: For the current node check whether it has a left child which is not there in the visited list. If it has then go to step-2 or else step-3.

Step-2: Put that left child in the list of visited nodes and make it your current node in consideration. Go to step-6.

Step-3: For the current node check whether it has a right child. If it has then go to step-4 else go to step-5

Step-4: Make that right child as your current node in consideration. Go to step-6.

Step-5: Check for the threaded node and if its there make it your current node.

Step-6: Go to step-1 if all the nodes are not over otherwise quit

public binarytree makethreadedinordertraversal(binarytree node, binarytree assignmentnode)
        {
            if (node == null)
            { return null; }
            assignmentnode = makethreadedinordertraversal(node.left, assignmentnode);
            if (assignmentnode != null)
            {
                assignmentnode.right = node;
                assignmentnode = null;
            }
            Console.WriteLine(node.data);
            if (node.right == null)
            {
                assignmentnode = node;
                return assignmentnode;
            }
            else
            {
                assignmentnode = makethreadedinordertraversal(node.right, assignmentnode);
                return assignmentnode;
            }
        }

use morris traversal.
geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
just awesome !!!

Iterative version. Slight modification in Morris Traversal.

void connectInorderSuccessor(Node* root)
{
	Node* current = root;
	
	while(current != NULL)
	{
		if(current->left == NULL)
		{
			current = current->right;
		}
		else
		{
			Node* pre = current->left;
			while(pre->right != NULL && pre->right != current)
			{
				pre = pre->right;
			}
			
			if(pre->right == NULL)
			{
				pre->right = current;
				current = current->left;
			}
			else
			{
				current = current->right;
			}
		}
	}
}

class Node
{
   Node left;
   Node right;
   Node parent;
   Node inorderS;
}

class TestTree{

Node findMinInRightTree(Node s)
{
   while(s.left != null) 
     s = s.left;
   return s;
}

Node findMinAbove(Node s)
{
   if(s.parent == null) return s;
   while(s.parent != null && s.parent.right = s)
        s = s.parent;
   return (s.parent==null) ? null : s;
}
   
Node updateNode(Node s)
{
   if(s.right == null) 
   {
       s.inorderS = findMinAbove(s);
       return s;
   }
   
   s.inorderS = findMinInRightTree(s);
   return updateNode(s.right);
}

// call updateNode(s) where s is root of tree to be updated. This is under assumption that only right most nodes of the tree are to be updated with the inorder successor

class Node
{
public:
	Node* left;
	Node* right;
	Node* Successor;
	char data;
	Node():left(NULL),right(NULL){}
};
void inorder(Node* node, Node* successor,bool right)
{
	if(node == NULL)
		return;
	inorder(node->left,node,false);
	if (right)node->Successor=successor;
	inorder(node->right,node,true);
}