Connect Nodes at the same level

Connect Nodes at the same level

  August 18, 2017    

---

Explanation :

Here we will insert root and null into queue.
Then perform BFS and mark next queue node to current node's next i.e.
p.nextRight = q.peek();

Then add its left and right subtree .

Check if queue has null in its current node it means that we are at last element of tree so remove that and add null to last of queue as queue already contains left , right subtrees of nodes of next level.

Repeat

Code:

class hackerranksolutionc
{
    void connect(Node root)
    {
        Queue<Node> q=new LinkedList<Node>();
        q.add(root);
        q.add(null);
        int h=0;
        while(!q.isEmpty())
        {
            Node temp=q.remove();
            if(temp!=null){
                temp.nextRight=q.peek();
                if(temp.left!=null)
            q.add(temp.left);
            if(temp.right!=null)
            q.add(temp.right);}
            else if(!q.isEmpty())
            q.add(null);
        }
    }

}


Without using extra space :

Here we will first mark next node of root to null then mark its left node to its right .

Check whether the next node is not empty find next suitable next by function and mark it.

GetNext () :

Here we will check the nextright node (it will be already marked by its root node) and check for its left tree , this left node will be next to the last node by which we are calling the function

    Node getNext(Node root)
    {
        Node temp=root.nextRight;
        while(temp!=null)
        {
            if(temp.left!=null)
            return temp.left;
            if(temp.right!=null)
            return temp.right;
            temp=temp.nextRight;
        }
        return null;
    }
    void connect(Node root)
    {
        if(root==null)
        return;
        root.nextRight=null;
        while(root!=null)
        {
            Node p=root;
            while(p!=null) // to mark every level
            {
                if(p.left!=null)
                {
                    if(p.right!=null)
                    p.left.nextRight=p.right;
                    else
                    p.left.nextRight=getNext(p);
                }
                if(p.right!=null)
                p.right.nextRight=getNext(p);
                p=p.nextRight;
            }
            if(root.left!=null)
            root=root.left;
            else if(root.right!=null)
            root=root.right;
            else
            root=getNext(root);
        }
    }