Binary Tree to DLL Geeks solution

Binary Tree to DLL Geeks solution

  July 23, 2017    

---

Problem:

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place.The order of nodes in DLL must be same as Inorder of the given Binary Tree

Idea:

Recur till the last (leaf node) and set previous and next

Code:

/*
Please note that it's Function problem i.e.
you need to write your solution in the form Function(s) only.
Driver Code to call/invoke your function would be added by GfG's Online Judge.*/


/* class Node
class Node
{
Node left, right;
int data;

Node(int d)
{
data = d;
left = right = null;
}

}*/
class hackerranksolutionc
{
    Node head;
    Node BtoDLL(Node root)
    {
        //if tree is empty
if(root==null)
return root;
if(root.left!=null)
{
   Node x=BtoDLL(root.left);
//go to last right node 
   for(;x.right!=null;x=x.right);
   x.right=root;
   root.left=x;
}
if(root.right!=null)
{
   Node y=BtoDLL(root.right);
   for(;y.left!=null;y=y.left);
   y.left=root;
   root.right=y;
}
return root;
    }
    Node BToDLL(Node root)
    {
        if(root==null)
return root;
head=BtoDLL(root);
while(head.left!=null)
head=head.left;
return head;

    }
}