CareerCup

/* last is a global/static variable*/

void inOrder(node *root){
    if (root==NULL) return;
    inOrder(root->left);
    if(last!=NULL)last->next = root;
    last = root;
    inOrder(root->right);
}

Node *end=NULL;
Node *beg=NULL;
void Inorder(Node *head)
{
if(head == NULL)
return ;
if(head->left)
Inorder(head->left);

if(beg==NULL)
{
beg=head;
end=head;
}
else
{
end->next=head;
end=head;
}


if(head->right)
Inorder(head->right);
}

Plese re write the question agian....Which pointer do we need to change..left or right....or is it just a new linked list we can create....like the one done above...

Assuming that the Tree structure could be changed. We can use a modified version of the Threaded binary tree. Here we are changing the 'right' TreeNode reference of a TreeNode. We pass on the last visited TreeNode through the recursion stack, and return the last visited TreeNode to the previous call of the recursion.

class TreeNode{
    TreeNode left = null;
    TreeNode right = null;
}

    private TreeNode inOrderLLTransf(TreeNode root, TreeNode predec){
        if(root == null){
            return null;
        }
        
        if(root.left!= null){
            predec = inOrderLLTransf(root.left, predec);
        }
        if(predec != null){
            predec.right = root;
        }
        predec = root;
        
        if(root.right != null){
            predec = inOrderLLTransf(root.right,predec);
        }               
        return predec;        
    }
    
    public void transformTree(TreeNode root){
        TreeNode lastVisited = inOrderLLTransf(root.right, null);
        if(lastVisited == null){
            //ERROR
        }
    }

for java

class PreNode
{
   TreeNode node = null;
}

public void addNext(TreeNode root, PreNode pre)
{
   if(root == null)
      return;
   addNext(root.left, pre);
   if(pre.node != null)
      pre.node.next = root;
   pre.node = root;
   addNext(root.right, pre)
}

This is the iterative solution using Stack in JAVA
public void flatten(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode previous = null;
while(!stack.empty()){
TreeNode current = stack.pop();
if (current.right!=null) {
stack.push(current.right);
}
if (current.left!=null) {
stack.push(current.left);
}
current.left = null;
current.right = null;

if (current == root) {
previous = current;
}
else{
previous.right = current;
previous = current;
}
}
}

Didn't understandthe question completely. Do we need to introduce an additional node to point to the inorder successor or we should change the existing pointers?

node* InorderList(node *root)
{
	if(root->right)
	{
		root->right->next = root->next;
		root->next = InorderList(root->right);
	}
	if(root->left)
	{
		root->left->next = root;
		return InorderList(root->left);
	}
	return root;
}