Convert a binary tree to doubly linked list

Given a binary tree, convert it into a doubly linked list as described:
1. We do not have to create a new linked list data structure. We have to convert the tree to a doubly linked list.
2. The doubly linked list should be created such that nodes follow inorder traversal of the binary tree.
3. Left node of the binary tree should be converted to the previous node of the doubly linked list.
4. Right node of the binary tree should be converted to the next node of the doubly linked list.
5. Left most node of the binary tree should be the head of the linked list.

Example:
Tree:
                    1
            2                3
        4        5        6        7

Output: 4 <-> 2 <-> 5 <-> 1 <-> 6 <-> 3 <-> 7


Question Asked in

Amazon, Facebook, Microsoft, Adobe


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

Process left subtree first:
    1. Move to the right most node of left subtree to get the inorder predecessor of the root, lets call is A.
    2. Now create doubly linked list pointers:
       a. Set the A.right to the root.
       b. Set root.left to A.
Process right subtree:
    1. Move to the left most node of right subtree to get the inorder successor of the root, lets call is B.
    2. Now create doubly linked list pointers:
       a. Set the B.left to the root.
       b. Set root.right to B.
Please go through algorithm visualization section and java code in code snippet section.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a binary tree, convert it into a doubly linked list
 *
 * @author Saurabh
 */
public class Tree {

	private Node root;
	
	public Node convertToDoublyLinkedList() {
		if (root == null) {
			return null;
		}

		root = convertToDoublyLinkedList(root);

		// Move to the leftmost node in the list
		while (root.getLeft() != null)
			root = root.getLeft();

		return root;
	}

	private Node convertToDoublyLinkedList(Node root) {
		
		if (root.getLeft() != null) {
			Node left = convertToDoublyLinkedList(root.getLeft());
			while (left.getRight() != null) {
				left = left.getRight();
			}
			left.setRight(root);
			root.setLeft(left);
		}
		
		if (root.getRight() != null) {
			Node right = convertToDoublyLinkedList(root.getRight());
			while (right.getLeft() != null) {
				right = right.getLeft();
			}
			right.setLeft(root);
			root.setRight(right);
		}

		return root;
	}
	
	/*
	 * Create a sample tree
	 * 				1
	 * 		2				3
	 * 4		5		6		7
	 *
	 */
	public void createSampleTree() {
		root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, new Node(6), new Node(7)));		
	}
	
	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.createSampleTree();
		Node linkedList = tree.convertToDoublyLinkedList();
		printList(linkedList);
	}

	public static void printList(Node linkedList) {
		System.out.println("Output:");
		while(linkedList != null) {
			System.out.print(linkedList.getData() + " ");
			linkedList = linkedList.getRight();
		}
	}
}

class Node {

	private int data;
	private Node left;
	private Node right;

	public Node(int data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public Node(int data) {
		this.data = data;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}
}
		

Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer