Binary Tree to Doubly Linked List

Java Implementation of converting a Binary Tree to Doubly Linked List

class Solution
{
    static class TreeNode{
        int data;
        TreeNode left,right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
    static TreeNode head;
    static TreeNode prev=null;
    static TreeNode BinaryTreeToDLL(TreeNode root)
    {
        if(root==null)
            return root;
        
	BinaryTreeToDLL(root.left);
        
	if(prev==null)
            head=root;
	else
	{
	    prev.right=root;
	    root.left=prev;
	}
	prev=root;
        
	BinaryTreeToDLL(root.right);
        
	return head;
    }
     public static void main(String[] args)
    {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        root.left.left=new TreeNode(4);
        root.left.right=new TreeNode(5);
        TreeNode head=BinaryTreeToDLL(root);
        
        TreeNode temp=head;
        while(temp!=null)
        {
            System.out.print(temp.data+" ");
            temp=temp.right;
        }
    }
    }

Output: 4 2 5 1 3

Time Complexity- O(n)

Space Complexity- O(n)

Leave a comment

Your email address will not be published. Required fields are marked *

Pin It on Pinterest