CareerCup

Isn't the solution of this one the same as quesiton#325695?

@above
No, This is different from question#325695.
In this question, all nodes in tree will be connected through next while in the previous question, only nodes at same levels will be connected through next.

We can do this during inorder traversal itself....keep a global pointer to prev node...

Node * prev;
inorder(Node* root) {
if(root->left != null)
inorder(root->left);

if(prev ==null )
prev= root;
else
{
prev->next = root;
prev= root;
}

if(root->right !=null)
inorder(root->right);
}

en.wikipedia.org/wiki/Threaded_binary_tree

This is very similar to the last post -

node_t *BSTNext(node_t *node){
if(node == null)
return null;

node_t *left = BSTNext(node->left);
if (left != null)
left->next = node;

node_t *right = BSTNext(node->right);
if (node->right != null)
node->next = right;

if(right != null)
return right;
else
return node;
}

void threadBST() {
  stack<Node*> s;
  Node* node = root;
  Node* prev = NULL;

  while (true) {
    if (node != NULL) {
      s.push(node);
      node = node->left;
    } else {
      if (!s.empty()) {
        node = s.top();
        s.pop();
        if (prev != NULL) prev->next = node;
        prev = node;
        node = node->right;
      } else {
        break;
      }
    }
  }
}

hi ryan can u pls explain ur code

point in this solution is to move from right to left because i don't have next from current node. Use global to set current to next and move to left.

node* next = null;
void linkNext(node* n)
{
if(n == null) return;

linkNext(n->right)
n->next = next;
next = n;
linkNext(n->left)
}

Morris In-order Traversal is used here
or
threaded binary tree

public static void MorrisTraversal(Node root)
        {
            Node current, pre;

            if (root == null)
                return;

            current = root;
            while (current != null)
            {
                if (current.Left == null)
                {
                    if (head1 == null)
                    {
                        head1 = current;
                        tail1 = current;
                    }
                    else
                    {
                        tail1.Next = current;
                        tail1 = current;
                    }
                    Console.WriteLine(current.ID);
                    current = current.Right;
                }
                else
                {
                    /* Find the inorder predecessor of current */
                    pre = current.Left;
                    while (pre.Right != null && pre.Right != current)
                        pre = pre.Right;

                    /* Make current as right child of its inorder predecessor */
                    if (pre.Right == null)
                    {
                        pre.Right = current;
                        current = current.Left;
                    }

                    /* Revert the changes made in if part to restore the original
                      tree i.e., fix the right child of predecssor */
                    else
                    {
                        pre.Right = null;

                        if (head1 == null)
                        {
                            head1 = current;
                            tail1 = current;
                        }
                        else
                        {
                            tail1.Next = current;
                            tail1 = current;
                        }
                        Console.WriteLine(current.ID);
                        current = current.Right;
                    } 
                } 
            } 
        }

        }

Inorder using stack and setting next when you hit left child as nul
l

public void populateNextUsingInOrder(TreeNode root){
		if(root == null) return;
		TreeNode node = root;
		Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
		while(node != null){
			stack.push(node);
			node = node.getLeftChild();
		}
		node = stack.peek();
		TreeNode current = null;
		TreeNode temp = null;
		while(!stack.isEmpty()){
			current = stack.pop();
			System.out.print(current.getKey()+ "--> " );
			temp = current.getRightChild();
			while(temp != null){
				stack.push(temp);
				temp = temp.getLeftChild();
			}
			current.setNext(stack.peek());
		}
		/*** FOR TESTING ***/
		System.out.println("\nTraverse using next from min");
		while(node != null){
			System.out.print(node.getKey()+ "--> " );
			node = node.getnext();
		}
	}