Convert a Binary Tree to Doubly Linked List

Posted in

Convert a Binary Tree to Doubly Linked List

Vinay Khatri
Last updated on June 10, 2022

    You are given a Binary Tree. Your task is to convert it into a doubly-linked list. The left and right child of the nodes of the Binary Tree is to be converted into previous and next pointers of the linked list respectively. Nodes of the doubly linked list must be according to the inorder of the binary tree. The leftmost node or the first node of the inorder of the tree will be the head of the tree.

    Approach 1

    In this approach, we will traverse the tree twice: first for fixing the left pointer and again for fixing the right pointer. Fixing the left pointer: This is the first step of this approach. We will iterate through the tree in an inorder fashion and will keep track of the previously visited node so that we could change the left pointer to the previous node. Fixing the right pointer: This is complex as compared to the previous step. We will be using the left pointers fixed in step one. Since the right-most node is the last node of the doubly linked list, we will start from there. We will traverse the tree linearly as the left pointers are already pointing to the previous nodes. We will keep track of the previously visited node and change the right pointer to the previous node during traversal.

    Algorithm

    1. Create a node with the value being set as the data that is passed as the parameter, and initializing its left and right children to NULL.
    2. Traverse the binary tree in inorder traversal, while updating the previous pointers in the list, with the left child nodes.
    3. Traverse the binary tree in inorder traversal, while updating the next pointers in the list, with the right child nodes.
    4. Traverse the tree and get the DLL's last node, or the node at the farthest right side in the tree
    5. Now, for updating the right pointers by traversing backward, from the farthest right node with the help of the left nodes.
    6. Traverse over the doubly linked list from the left node to the right node to print it.

    The implementation of the above-discussed approach is:

    CPP

    #include <bits/stdc++.h>
    using namespace std;
    
    // Class for a node
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    class node
    {
      public:
      int data;
      node *left, *right;
    };
    
    // function to create a node
    // with the value being set as the data
    // that is passed as the parameter,
    // and initializing its left and right children to NULL
    node *newNode(int data)
    {
      node *Node = new node();
      Node->data = data;
      Node->left = Node->right = NULL;
      return(Node);
    }
    
    // function to traverse tree in an
    // inorder fashion
    void inorder(node *root)
    {
      if (root != NULL)
      {
        inorder(root->left);
        cout << " " << root->data;
        inorder(root->right);
      }
    }
    
    // function to traverse the binary tree
    // in inorder traversal, while
    // updating the previous pointers
    // in the list, with the left child nodes.
    void setPrevPtr(node *root)
    {
      static node *pre = NULL;
    
      if (root != NULL)
      {
        setPrevPtr(root->left);
        root->left = pre;
        pre = root;
        setPrevPtr(root->right);
      }
    }
    
    // function to traverse the binary tree
    // in inorder traversal, while
    // updating the next pointers
    // in the list, with the right child nodes.
    node *setNextPtr(node *root)
    {
      node *prev = NULL;
    
      // to traverse the tree and 
      // get the DLL's last node, or 
      // the node at farthest right side 
      // in the tree
      while (root && root->right != NULL)
        root = root->right;
    
      // now, for updating the right pointers 
      // by traversing backwards, 
      // from the farthest right node
      // with the help of the left nodes.
      while (root && root->left != NULL)
      {
        prev = root;
        root = root->left;
        root->right = prev;
      }
    
      // return the head of the linked list
      // i.e., the node at the farthest left side.
      return (root);
    }
    
    // function to transform the binary tree
    // into doubly linked lists.
    node *convertBT(node *root)
    {
      // for the setting of the previous pointer
      setPrevPtr(root);
    
      // for the setting of the next pointer
      return setNextPtr(root);
    }
    
    // to print, traverse over the doubly linked list
    // from the left node to the right node.
    void printDLL(node *root)
    {
      while (root != NULL)
      {
        cout<<" "<data;
        root = root->right;
      }
    }
    
    // Driver code
    int main(void)
    {
      node *root = newNode(10);
      root->left = newNode(12);
      root->right = newNode(15);
      root->left->left = newNode(25);
      root->left->right = newNode(30);
      root->right->left = newNode(36);
    
      cout<<"Inorder Tree:\n";
      inorder(root);
    
      node *head = convertBT(root);
    
      cout << "\nConverted Doubly Linked List:\n";
      printDLL(head);
      return 0;
    }
    
    

    Output

    Inorder Tree:
     25 12 30 10 36 15
    Converted Doubly Linked List:
     25 12 30 10 36 15

    JAVA

    public class ConvertBT
    {
    	static class node
    	{
    		int data;
    		node left, right;
    
    		public node(int data)
    		{
    			this.data = data;
    		}
    	}
    
    	static node prev;
    
    	// function to traverse the binary tree
    	// in inorder traversal, while
    	// updating the previous pointers
    	// in the list, with the left child nodes.
    	static void setPrevPtr(node root)
    	{
    		if (root == null)
    			return;
    
    		setPrevPtr(root.left);
    		root.left = prev;
    		prev = root;
    		setPrevPtr(root.right);
    
    	}
    
    	// function to traverse the binary tree
    	// in inorder traversal, while
    	// updating the next pointers
    	// in the list, with the right child nodes.
    	static node setNextPtr(node root)
    	{		
    		// to traverse the tree and 
    		// get the DLL's last node, or 
    		// the node at farthest right side 
    		// in the tree
    		while (root.right != null)
    			root = root.right;
    
    		// now, to updating the right pointers 
    		// by traversing backwards, 
    		// from the farthest right node
    		// with the help of the left nodes.
    		while (root != null && root.left != null)
    		{
    			node left = root.left;
    			left.right = root;
    			root = root.left;
    		}
    
    		// return the head of the linked list
    		// i.e., the node at the farthest left side.
    		return root;
    	}
    
    	// method to transform the binary tree
    	// into doubly linked list.
    	static node BTTtoDLL(node root)
    	{
    		prev = null;
    
    		// for the setting of the previous pointer
    		setPrevPtr(root);
    
    		// for the setting of the next pointer
    		return setNextPtr(root);
    	}
    
    	// to print, traverse over the doubly linked list
    	// from the left node to the right node.
    	static void printDLL(node root)
    	{
    		while (root != null)
    		{
    		    System.out.print(" ");
    			System.out.print(root.data + " ");
    			root = root.right;
    		}
    	}
    
    	// function to traverse tree in an
    	// inorder fashion
    	static void inorder(node root)
    	{
    		if (root == null)
    			return;
    		inorder(root.left);
    		System.out.print(" ");
    		System.out.print(root.data + " ");
    		inorder(root.right);
    	}
    
    	public static void main(String[] args)
    	{
    		node root = new node(10);
    		root.left = new node(12);
    		root.right = new node(15);
    		root.left.left = new node(25);
    		root.left.right = new node(30);
    		root.right.left = new node(36);
    
    		System.out.println("Inorder Tree:");
    		inorder(root);
    
    		node head = BTTtoDLL(root);
    
    		System.out.println("\nConverted Doubly Linked List:");
    		printDLL(head);
    	}
    }
    

    Output

    Inorder Tree:
     25 12 30 10 36 15
    Converted Doubly Linked List:
     25 12 30 10 36 15

    Python

    # Class for a node
    # having an integer value, data
    # and two pointers
    # to store the references of the
    # left and right children
    class Node:
        
        # constructor to create a node
        # with the value being set as the data
        # that is passed as the parameter,
        # and initializing its left and right children to NULL
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None
    
    # function to traverse tree in an
    # inorder fashion
    def inorder(root):
        
        if root is not None:
            inorder(root.left)
            print (" %d" %(root.data))
            inorder(root.right)
    
    # function to traverse the binary tree
    # in inorder traversal, while
    # updating the previous pointers
    # in the list, with the left child nodes.
    def setPrevPtr(root):
        if root is not None:
            setPrevPtr(root.left)
            root.left = setPrevPtr.pre
            setPrevPtr.pre = root
            setPrevPtr(root.right)
    
    # function to traverse the binary tree
    # in inorder traversal, while
    # updating the next pointers
    # in the list, with the right child nodes.
    def setnextPtr(root):
    
        prev = None
        # to traverse the tree and 
        # get the DLL's last node, or 
        # the node at farthest right side 
        # in the tree
        while(root and root.right != None):
            root = root.right
    
        # now, to updating the right pointers 
        # by traversing backwards, 
        # from the farthest right node
        # with the help of the left nodes.
        while(root and root.left != None):
            prev = root
            root = root.left
            root.right = prev
    
        # return the head of the linked list
        # i.e., the node at the farthest left side.
        return root
    
    # function to transform the binary tree
    # into a doubly linked list.
    def ConvertBT(root):
        
        # for the setting of the previous pointer
        setPrevPtr(root)
    
        # for the setting of the next pointer
        return setnextPtr(root)
    
    # to print, traverse over the doubly linked list
    # from the left node to the right node.
    def printDLL(root):
        while(root != None):
            print (" %d" %(root.data))
            root = root.right
    
    # Driver program to test above function
    root = Node(10)
    root.left = Node(12)
    root.right = Node(15)
    root.left.left = Node(25)
    root.left.right = Node(30)
    root.right.left = Node(36)
    
    print ("Inorder Tree:")
    inorder(root)
    
    setPrevPtr.pre = None
    head = ConvertBT(root)
    
    print ("\nConverted Doubly Linked List:")
    printDLL(head)
    

    Output

    Inorder Tree:
     25 12 30 10 36 15
    Converted Doubly Linked List:
     25 12 30 10 36 15

    Time Complexity: O(n), where n is the number of nodes. Because we are simply traversing the tree twice in the inorder fashion.

    Approach 2

    This approach is simpler than the previous one. In this approach, we will iterate over the tree in the inorder fashion and keep a track of the node that has been traversed, let’s say prev. Now, for every visited node, update it as the next of prev and previous of this node as prev .

    Algorithm

    1. Recursively convert the binary tree whose root has been passed to it as a parameter to a doubly linked list, whose head has also been passed to it as a parameter.
    2. Convert recursively the right subtree into dll.
    3. Place the root of the binary tree into the doubly linked list.
    4. Update the previous head using the left pointer
    5. Update the dll's head
    6. Print, traverse over the doubly linked list.
    7. Convert recursively the right subtree into dll.
    8. From the left node to the right node.
    9. Traverse from left node to right node to print.

    The implementation of the above-discussed approach is:

    CPP

    `#include <bits/stdc++.h>
    using namespace std;
    // Structure for a node and tree
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    struct Node {
      int data;
      Node *left, *right;
    };
    
    // function to create a node
    // with the value being set as the data
    // that is passed as the parameter,
    // and initializing its left and right children to NULL
    Node* newNode(int data)
    {
      Node* node = new Node;
      node->data = data;
      node->left = node->right = NULL;
      return node;
    }
    
    // function to recursively convert the binary tree
    // whose root has been passed to it as a parameter
    // to a doubly-linked list, whose head has also been passed
    // to it as a parameter.
    void ConvertBT(Node* root, Node*& head)
    {
      // Base cases
      if (root == NULL)
        return;
    
      // convert recursively the right subtree
      // into dll.
      ConvertBT(root->right, head);
    
      // placing the root of the
      // binary tree into the 
      // doubly linked list.
      root->right = head;
    
      // updating the previous head
      // using the left pointer
      if (head != NULL)
        head->left = root;
    
      // updating the dll's head
      head = root;
    
      // convert recursively the left subtree
      // into dll.
      ConvertBT(root->left, head);
    }
    
    // to print, traverse over the doubly linked list
    // from the left node to the right node.
    void printDLL(Node* head)
    {
      cout << "Converted Doubly Linked List:\n";
      while (head) {
        cout << " " << head->data;
        head = head->right;
      }
    }
    
    int main()
    {
    
      Node *root = newNode(10);
      root->left = newNode(12);
      root->right = newNode(15);
      root->left->left = newNode(25);
      root->left->right = newNode(30);
      root->right->left = newNode(36);
    
      Node* head = NULL;
      ConvertBT(root, head);
    
      printDLL(head);
    
      return 0;
    }
    

    Output

    Converted Doubly Linked List:
     25 12 30 10 36 15

    JAVA

    // class for a node and tree
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    class Node {
    	int data;
    	Node left, right;
    
    	public Node(int data)
    	{
    		this.data = data;
    		left = right = null;
    	}
    }
    
    class BinaryTree {
    	Node root;
    	Node head;
    
    	// function to recursively convert the binary tree
    	// whose root has been passed to it as a parameter
    	// to a doubly linked list, whose head as also been passed
    	// to it as a parameter.
    	void ConverBT(Node root)
    	{
    		// Base cases
    		if (root == null)
    			return;
    
    		// convert recursively the right subtree
    		// into dll
    		ConverBT(root.right);
    
    		// placing the root of the
    		// binary tree into the 
    		// doubly linked list.
    		root.right = head;
    
    		// updating the previous head
    		// using the left pointer
    		if (head != null)
    			head.left = root;
    
    		// updating the dll's head
    		head = root;
    
    		// convert recursively the left subtree
    		// into dll.
    		ConverBT(root.left);
    	}
    
    	// to print, traverse over the doubly lined list
    	// from the left node to the right node.
    	void printDLL(Node head)
    	{
    		System.out.println("Converted Doubly Linked List:");
    		while (head != null) {
    			System.out.print(head.data + " ");
    			head = head.right;
    		}
    	}
    
    	public static void main(String[] args)
    	{
    
    		BinaryTree tree = new BinaryTree();
    		tree.root = new Node(10);
    		tree.root.left = new Node(12);
    		tree.root.right = new Node(15);
    		tree.root.left.left = new Node(25);
    		tree.root.left.right = new Node(30);
    		tree.root.right.left = new Node(36);
    
    		tree.ConverBT(tree.root);
    		tree.printDLL(tree.head);
    	}
    }
    

    Output

    Converted Doubly Linked List:
    25 12 30 10 36 15

    Python

    # class for a node and tree
    # having an integer value, data
    # and two pointers
    # to store the references of the
    # left and right children
    class Node:
        def __init__(self, data):
            self.data = data
            self.left = self.right = None
    
    class BinaryTree:
        # function to recursively convert the binary tree
        # whose root has been passed to it as a parameter
        # to a doubly linked list, whose head as also been passed
        # to it as a parameter.
        root, head = None, None
        
        def ConvertBT(self, root: Node):
            if root is None:
                return
    
            # convert recursively the right subtree
            # into dll
            self.ConvertBT(root.right)
    
         
            # placing the root of the
            # binary tree into the
            # doubly linked list.
            root.right = self.head
    
            # updating the previous head
            # using the left pointer
            if self.head is not None:
                self.head.left = root
    
            # updating the dll's head
            self.head = root
    
            # convert recursively the left subtree
            # into dll
            self.ConvertBT(root.left)
    
        def printDLL(self, head: Node):
            print('Converted Doubly Linked List:')
            while head is not None:
                print(head.data, end = ' ')
                head = head.right
    
    if __name__ == '__main__':
        
        tree = BinaryTree()
        tree.root = Node(10)
        tree.root.left = Node(12)
        tree.root.right = Node(15)
        tree.root.left.left = Node(25)
        tree.root.left.right = Node(30)
        tree.root.right.left = Node(36)
    
        tree.ConvertBT(tree.root)
        tree.printDLL(tree.head)
    

    Output

    Converted Doubly Linked List:
    25 12 30 10 36 15

    Time Complexity: O(n), where n is the number of nodes. Because we are simply applying the inorder traversal.

    Approach 3

    The basic idea of this approach is that we perform the inorder traversal over the tree. Add nodes at the starting of the current linked list and update the head of the list. Because we are adding the node at the start, we have to operate leaf nodes in the reverse order.

    Algorithm

    1. Create a static variable to store the node visited previously.
    2. Convert recursively the left subtree into dll.
    3. Convert recursively the right subtree into dll.
    4. Traverse over the doubly linked lis from the left node to the right node to print.

    The implementation of the above-discussed approach is

    CPP

    #include 
    using namespace std;
    
    // Structure for a node
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    struct node
    {
      int data;
      node* left;
      node* right;
    };
    
    // function to recursively convert the binary tree
    // whose root has been passed to it as a parameter
    // to a doubly-linked list, whose head as also been passed
    // to it as a parameter.
    void ConvertBT(node *root, node **head)
    {
      // Base case
      if (root == NULL) return;
    
      // static variable to
      // store the node visited previously.
      // initialize it to null 
      static node* prev = NULL;
    
      // convert recursively the left subtree
      // into dll.
      ConvertBT(root->left, head);
    
      if (prev == NULL)
        *head = root;
      else
      {
        root->left = prev;
        prev->right = root;
      }
      prev = root;
    
      // convert recursively the right subtree
      // into dll.
      ConvertBT(root->right, head);
    }
    
    // function to create a node
    // with the value being set as the data
    // that is passed as the parameter,
    // and initializing its left and right children to NULL
    node* newNode(int data)
    {
      node* new_node = new node;
      new_node->data = data;
      new_node->left = new_node->right = NULL;
      return (new_node);
    }
    
    // to print, traverse over the doubly linked list
    // from the left node to the right node.
    void printDLL(node *node)
    {
      while (node!=NULL)
      {
        cout << node->data << " "; node = node->right;
      }
    }
    
    int main()
    {
      node *root   = newNode(10);
      root->left   = newNode(12);
      root->right  = newNode(15);
      root->left->left = newNode(25);
      root->left->right = newNode(30);
      root->right->left = newNode(36);
    
      node *head = NULL;
      ConvertBT(root, &head);
    
      cout << "\nConverted Doubly Linked List:\n";
      printDLL(head);
    
      return 0;
    }
    

    Output

    Converted Doubly Linked List:
    25 12 30 10 36 15

    JAVA

    // Class for a node
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    class Node
    {
      int data;
      Node left, right;
    
      public Node(int data)
      {
        this.data = data;
        left = right = null;
      }
    }
    
    class BinaryTree
    {
      Node root;
      Node head;
      
      // static variable to
      // store the node visited previously.
      // initialize it to null 
      static Node prev = null;
    
      // function to recursively convert the binary tree
      // whose root has been passed to it as a parameter
      // to a doubly linked list, whose head as also been passed
      // to it as a parameter.
      void ConvertBT(Node root)
      {
        // Base case
        if (root == null)
          return;
    
        // convert recursively the left subtree
        // into dll.
        ConvertBT(root.left);
    
        if (prev == null)
          head = root;
        else
        {
          root.left = prev;
          prev.right = root;
        }
        prev = root;
    
        // convert recursively the right subtree
        // into dll.
        ConvertBT(root.right);
      }
    
      // to print, traverse over the doubly linked list
      // from the left node to the right node.
      void printDLL(Node node)
      {
        while (node != null)
        {
          System.out.print(node.data + " ");
          node = node.right;
        }
      }
    
      public static void main(String[] args)
      {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(12);
        tree.root.right = new Node(15);
        tree.root.left.left = new Node(25);
        tree.root.left.right = new Node(30);
        tree.root.right.left = new Node(36);
    
        tree.ConvertBT(tree.root);
        System.out.println("\nConverted Doubly Linked List:");
        tree.printDLL(tree.head);
    
      }
    }
    

    Output

    Converted Doubly Linked List:
    25 12 30 10 36 15

    Python

    class Node:
        def __init__(self, val):
            self.right = None
            self.data = val
            self.left = None
    
    
    class BtoDll:
        def __init__(self):
            self.head = None
            self.tail = None
    
        def convert(self, root):
        
            # Base case
            if root is None:
                return
            
            # convert recursively the left subtree
            # into dll.
            self.convert(root.left)
    
            node = root
            if self.head is None:
                self.head = node
            else:
                self.tail.right = node
                node.left = self.tail
            self.tail = node
            
            # convert recursively the right subtree
            # into dll.
            self.convert(root.right)
            return self.head
    
    
    def ConvertBT(root):
        # function to recursively convert the binary tree
        # whose root has been passed to it as a parameter
        # to a doubly linked list, whose head as also been passed
        # to it as a parameter.
        converter = BtoDll()
        return converter.convert(root)
    
    
    def printDLL(head):
        # to print, traverse over the doubly linked list
        # from the left node to the right node.
        while head is not None:
            print(head.data, end=" ")
            head = head.right
    
    
    if __name__ == "__main__":
    
        root = Node(10)
        root.left = Node(12)
        root.right = Node(15)
        root.left.left = Node(25)
        root.left.right = Node(30)
        root.right.left = Node(36)
        
        head = ConvertBT(root)
        print("Converted Doubly Linked List:")
        printDLL(head)
    

    Output

    Converted Doubly Linked List:
    25 12 30 10 36 15

    Time Complexity: O(n), where n is the number of nodes, as we are applying simple in order traversal.

    Wrapping Up!

    In this article, we have learned an amazing concept of Binary Trees. Binary Tree is one of the most important data structures and is usually asked in the top interview questions as well. “Convert a Binary Tree into a doubly-linked list” is a popular as well as a very important problem that has been asked in various interview questions. We also covered in detail how all the three approaches work and what are the significance of them respectively. We discussed their time complexity as well as space complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers can refer to this article. That’s why, this article also contains well-explained codes for all the three approaches in the three most popular languages which are c++, Java, and python along with their respective outputs attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of Binary Trees and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article. Happy Learning! People are also reading:

    Leave a Comment on this Post

    0 Comments