Binary Tree to Doubly Linked List Editorial

Practice Problem Link: Binary Tree to Doubly Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A binary tree can be converted into a doubly linked list (DLL) whose traversal will give the tree's inorder traversal.

Use the left and right pointers of a tree node as previous and next pointers respectively in the DLL.

Given the root node, convert the binary tree into a doubly linked list, in-place. Return the head of the DLL.

Approach

Since the DLL should be in the inorder traversal of the tree, the idea is to convert the tree recursively by doing inorder traversal of the tree.

• Recursively convert the left subtree.
• To convert the current node, set the right pointer of its previously visited node to the current node and the left pointer of the current node to the previously visited node. Update the previously visited node to the current node.
• Recursively convert the right subtree.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
Node* prevNode, *head;
void binaryTreeToDll(Node* root) {
	if (root == NULL) {
		return;
	}
	binaryTreeToDll(root->left);
	if (prevNode == NULL) {
		head = root;
	} else {
		root->left = prevNode;
		prevNode->right = root;
	}
	prevNode = root;
	binaryTreeToDll(root->right);
}
Node* binaryTreeToDoublyLinkList(Node* root) {
    prevNode = NULL;
	binaryTreeToDll(root);
	return head;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	Node prevNode, head;
	void binaryTreeToDll(Node root) {
		if (root == null) {
			return;
		}
		binaryTreeToDll(root.left);
		if (prevNode == null) {
			head = root;
		} else {
			root.left = prevNode;
			prevNode.right = root;
		}
		prevNode = root;
		binaryTreeToDll(root.right);
	}
	Node binaryTreeToDoublyLinkList(Node root) {
		prevNode = null;
	    binaryTreeToDll(root);
		return head;
	}
}