Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

November 29, 2010 in binary tree, linked list

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

If the problem statement is still not clear to you, below is a pictorial representation of what you need to do:

i) an ordered binary tree (BST) storing numbers from 1 – 5.

ii) original tree converted to a sorted circular doubly-linked list. Its left and right pointers were modified to point to its previous and next node.

I originally read this interesting problem here: The Great Tree-List Recursion Problem.

Hint:
Think of in-order traversal. How do you ensure that the last element’s right pointer points back to the first element?

A circular doubly-linked list. Think of the left and right pointers in a tree as synonymous to the previous and next pointers in a list.

Solution:
When I first see this problem, my first thought was in-order traversal. Couldn’t we modify the nodes’ left and right pointers as we do an in-order traversal of the tree? However, we have to beware not to modify the pointers and accessing it at a later time.

As we traverse the tree in-order, we could safely modify a node’s left pointer to point to the previously traversed node as we never use it once we reach a node. We would also need to modify the previously traversed node’s right pointer to point to the current node. Note: The previously traversed node meant here is not its parent node. It is the node’s previous smaller element.

Easy approach, right? But wait, we are still missing two more steps. First, we did not assign the list’s head pointer. Second, the last element’s right pointer does not point to the first element (similar to the first element’s left pointer).

How do we solve this? My approach is pretty easy: Just update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automagically updated with the correct pointers. Don’t forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.

A double-linked list with a length of one.

Do you think this approach works? I bet it did! The run time complexity for this solution is O(N) since we are essentially doing a modified in-order traversal. It does have some extra assignments in each recursive call though. But overall I am quite satisfied with this approach because it is intuitive and easy to follow. Besides, we are adapting an existing algorithm (in-order traversal) to solve this problem, isn’t this just neat?

// This is a modified in-order traversal adapted to this problem.
// prev (init to NULL) is used to keep track of previously traversed node.
// head pointer is updated with the list's head as recursion ends.
void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
  if (!p) return;
  treeToDoublyList(p->left, prev, head);
  // current node's left points to previous node
  p->left = prev;
  if (prev)
    prev->right = p;  // previous node's right points to current node
  else
    head = p; // current node (smallest element) is head of
              // the list if previous node is not available
  // as soon as the recursion ends, the head's left pointer 
  // points to the last node, and the last node's right pointer
  // points to the head pointer.
  Node *right = p->right;
  head->left = p;
  p->right = head;
  // updates previous node
  prev = p;
  treeToDoublyList(right, prev, head);
}

// Given an ordered binary tree, returns a sorted circular
// doubly-linked list. The conversion is done in-place.
Node* treeToDoublyList(Node *root) {
  Node *prev = NULL;
  Node *head = NULL;
  treeToDoublyList(root, prev, head);
  return head;
}

// This is a modified in-order traversal adapted to this problem.

// prev (init to NULL) is used to keep track of previously traversed node.

// head pointer is updated with the list's head as recursion ends.

void treeToDoublyList(Node *p, Node *& prev, Node *& head) {

if (!p) return;

treeToDoublyList(p->left, prev, head);

// current node's left points to previous node

p->left = prev;

if (prev)

prev->right = p; // previous node's right points to current node

else

head = p; // current node (smallest element) is head of

// the list if previous node is not available

// as soon as the recursion ends, the head's left pointer

// points to the last node, and the last node's right pointer

// points to the head pointer.

Node *right = p->right;

head->left = p;

p->right = head;

// updates previous node

prev = p;

treeToDoublyList(right, prev, head);

}

// Given an ordered binary tree, returns a sorted circular

// doubly-linked list. The conversion is done in-place.

Node* treeToDoublyList(Node *root) {

Node *prev = NULL;

Node *head = NULL;

treeToDoublyList(root, prev, head);

return head;

}

Alternative Solution:
There is an alternative solution which doesn’t use in-order traversal. Instead, it uses a divide and conquer method which is quite neat. I highly recommend you to read the solution (code provided) here.

Rating: 4.5/5 (2 votes cast)

Convert Binary Search Tree (BST) to Sorted Doubly-Linked List, 4.5 out of 5 based on 2 ratings

← Convert Sorted List to Balanced Binary Search Tree (BST)

CTRL+A, CTRL+C, CTRL+V →

19 responses to Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

Anonymous said on December 5, 2010
The Alternative Solution's use of recursion just BLEW MY MIND! Amazing solution, using the power of recursion.
VA:F [1.9.22_1171]
0
Reply
Greed said on April 13, 2011
The solutions you provide are really very nice . I have a question and i am not able to solve it .Please help!!
Question is “Vertical order traversal of a binary tree.”
VA:F [1.9.22_1171]
-1
Reply
J.W. said on May 2, 2011
Very nice solution, thanks for sharing.
VA:F [1.9.22_1171]
0
Reply
- ravenchen1204 said on December 11, 2012
  I have two solution
  sol one:
  run time O(N)
  space O(N)
  sol two:
  run time O(N^2)
  space O(1)
  if you are interested in those two solutions, let me no
  VA:F [1.9.22_1171]
  -1
  Reply

HX said on June 9, 2011

Another solution is to use post-order traverse. The idea is that for each node (considered as a sub tree), we find two pointers that point to its minimum and maximum child. Then we can make the linked list by:
this_node->left_child->max —-> this_node;
this_node-> —-> this_node->right_child->min;

NOTE: I realize that the following code can generate a single link only. Need more thoughts how to modify it to generate double-linked list.

//============================================
void postorder(node * n, node * & min, node * & max)
{
  node * child_min;
  node * child_max;  // used to get left/right child's min/max pointers

  if (!n->left) 
  {
    child_min = n;
  }
  else
  {
    postorder(n->left, child_min, child_max);
    child_max->right = n;  // link child_max (right most node in the left sub tree) to this node
  }
  min = child_min;

  if (!n->right)
  {
    child_max = n;
  }
  else
  {
    postorder(n->right, child_min, child_max);
    n->right = child_min;  // link this node to (left most node in the right sub tree)
  }
  max = child_max;
}

void main()
{
  node * child_min;
  node * child_max;
  node * root = ...;

  postorder(root, child_min, child_max);
  child_min->left = child_max;
  child_max->right = child_min;
}

//============================================

void postorder(node * n, node * & min, node * & max)

{

node * child_min;

node * child_max; // used to get left/right child's min/max pointers

if (!n->left)

{

child_min = n;

}

else

{

postorder(n->left, child_min, child_max);

child_max->right = n; // link child_max (right most node in the left sub tree) to this node

}

min = child_min;

if (!n->right)

{

child_max = n;

}

else

{

postorder(n->right, child_min, child_max);

n->right = child_min; // link this node to (left most node in the right sub tree)

}

max = child_max;

}

void main()

{

node * child_min;

node * child_max;

node * root = ...;

postorder(root, child_min, child_max);

child_min->left = child_max;

child_max->right = child_min;

}

SkyWalker said on June 26, 2011
Hey 1337,
I’ve tried an alternate solution, making use of a global node which keeps track of the last modified node.
The code can be found here: http://collabedit.com/tknj8
Please note, this doesn’t create a doubly sorted circular list.
I wanted your thoughts about this solution and any possible bugs.
Thanks.
VA:F [1.9.22_1171]
0
Reply
Rvp said on July 28, 2011
Absolutely awesome!!! saw an alternate solution in stanford site but this is totally awesome
Keep up the great work mate,cheers!!!
VA:F [1.9.22_1171]
0
Reply
www said on August 8, 2011
very impressive!! great job!
VA:F [1.9.22_1171]
0
Reply
LoneShadow said on August 20, 2011
Wouldnt this work as well?
void
bsttodll(struct node *rootp, struct node **prevp, struct node **headp){
if (!rootp) return;
bsttodll(rootp->left, prevp, headp);
rootp->left = *prevp;
if (!*headp)
*headp = rootp;
if (*prevp)
(*prevp)->right = rootp;
*prevp = rootp;
bsttodll(rootp->right, prevp, headp);
}
VA:F [1.9.22_1171]
+1
Reply
LoneShadow said on August 20, 2011
I guess it needs the special case, when recursion ends, the head and the final node need to be connected.
VA:F [1.9.22_1171]
0
Reply
Pritam said on August 24, 2011
Hey I have written this code..but this does not give the correct output..
e.g if tree is
13
8 20
3 9 15 25
output is – 13,20,25
i.e head pointer n d right subtree..
I don’t know why for left subtree elements, head is getting updated everytime..
Please tell me what is the wrong thing in this..
struct node *doubly(struct node *t,struct node *prev, struct node *head)
{
if(t==NULL)
return;
doubly(t->left,prev,head);
t->left = prev;
if(prev != NULL)
prev->right=t;
else
head=t;
struct node *right = t->right;
head->left=t;
t->right=head;
prev = t;
doubly(right,prev,head);
return head;
}
treeToDoubly(struct node *t)
{
struct node *prev = NULL;
struct node *head = NULL;
head = doubly(t,prev,head);
printf(“List is \n”);
for(temp=head;temp->right!=head;temp=temp->right)
printf(“%d,”,temp->data);
printf(“%d”,temp->data);
}
VA:F [1.9.22_1171]
0
Reply
taskin said on March 11, 2012
hi i have a question if (!p) return; it returns what?i am new to programming:)
VA:F [1.9.22_1171]
0
Reply
stormclass said on May 4, 2012
my solution is similar, but i think it is very easy to understand.
class Solution {
public:
pair convertTreeRecursive(Node *root) {
if (root == NULL) {
return pair(NULL, NULL);
}
pair left = convertTreeRecursive(root->left);
pair right = convertTreeRecursive(root->right);
Node *prevLeft = left.first;
Node *lastLeft = left.second;
Node *prevRight = right.first;
Node *lastRight = right.second;
if (lastLeft) {
lastLeft->right = root;
root->left = lastLeft;
}
if (prevRight) {
prevRight->left = root;
root->right = prevRight;
}
return pair(prevLeft == NULL ? root : prevLeft,
lastRight == NULL ? root : lastRight);
}
Node * convertTree(Node *root) {
if (root == NULL) {
return NULL;
}
pair ret = convertTreeRecursive(root);
(ret.first)->left = ret.second;
(ret.second)->right = ret.first;
return ret.first;
}
};
VA:F [1.9.22_1171]
0
Reply

Jinhui said on July 16, 2012

void InOrder(Node* parent, Node*& first, Node*& last)
{
	if(NULL == parent->left)
		first = parent;
	else
	{
		Node* tmpLast;
		InOrder(parent->left, first, tmpLast);
		parent->left = tmpLast;
		tmpLast->right = parent;
	}
	
	if (NULL == parent->right)
		last = parent;
	else
	{
		Node* tmpFirst;
		InOrder(parent->right, tmpFirst, last);
		parent->right = tmpFirst;
		tmpFirst->left = parent;
	}
}

Node* TreeToList(Node* root)
{
	if(NULL == root) return NULL;
	
	Node* first;
	Node* last;
	InOrder(root, first, last);
	first->left = last;
	last->right = first;
	
	return first;
}

void InOrder(Node* parent, Node*& first, Node*& last)

{

if(NULL == parent->left)

first = parent;

else

{

Node* tmpLast;

InOrder(parent->left, first, tmpLast);

parent->left = tmpLast;

tmpLast->right = parent;

}

if (NULL == parent->right)

last = parent;

else

{

Node* tmpFirst;

InOrder(parent->right, tmpFirst, last);

parent->right = tmpFirst;

tmpFirst->left = parent;

}

Node* TreeToList(Node* root)

{

if(NULL == root) return NULL;

Node* first;

Node* last;

InOrder(root, first, last);

first->left = last;

last->right = first;

return first;

}

LT said on October 26, 2012

public class BST2DoubledLinkedList {
	
	public TreeNode convert(TreeNode root) {
		TreeNode head = new TreeNode();
		
		TreeNode first = minNode(root);
		TreeNode last = maxNode(root);
		convert2DoubledLinkedList(root);
		
		first.left = last;
		last.right = first;
		head.right = first;
		return head;
	}
	
	public TreeNode minNode(TreeNode node) {
		if (node.left == null) {
			return node;
		} else 
			return minNode(node.left);
	}
	
	public TreeNode maxNode(TreeNode node) {
		if (node.right == null) {
			return node;
		} else 
			return maxNode(node.right);
	}
	public void convert2DoubledLinkedList(TreeNode root) {
		if (root.left == null && root.right == null)
			return;

		convert2DoubledLinkedList(root.left);
		rightMost(root, root.left);
		convert2DoubledLinkedList(root.right);
		leftMost(root, root.right);

	}

	private void leftMost(TreeNode root, TreeNode node) {
		if (node.left != null) {
			leftMost(root, node.left);
		} else {
			node.left = root;
			root.right = node;
		}
	}

	private void rightMost(TreeNode root, TreeNode node) {
		if (node.right != null) {
			rightMost(root, node.right);
		} else {
			node.right = root;
			root.left = node;
		}
	}
}

public class BST2DoubledLinkedList {

public TreeNode convert(TreeNode root) {

TreeNode head = new TreeNode();

TreeNode first = minNode(root);

TreeNode last = maxNode(root);

convert2DoubledLinkedList(root);

first.left = last;

last.right = first;

head.right = first;

return head;

}

public TreeNode minNode(TreeNode node) {

if (node.left == null) {

return node;

} else

return minNode(node.left);

}

public TreeNode maxNode(TreeNode node) {

if (node.right == null) {

return node;

} else

return maxNode(node.right);

}

public void convert2DoubledLinkedList(TreeNode root) {

if (root.left == null && root.right == null)

return;

convert2DoubledLinkedList(root.left);

rightMost(root, root.left);

convert2DoubledLinkedList(root.right);

leftMost(root, root.right);

}

private void leftMost(TreeNode root, TreeNode node) {

if (node.left != null) {

leftMost(root, node.left);

} else {

node.left = root;

root.right = node;

}

private void rightMost(TreeNode root, TreeNode node) {

if (node.right != null) {

rightMost(root, node.right);

} else {

node.right = root;

root.left = node;

}

A said on December 28, 2012

struct TreeNode {
	int val;
	struct TreeNode *left, *right, *parent;
} *root;

typedef struct TreeNode Node;

Node** BST_To_DoublyLL2(Node* root) {
	Node** result = (Node **) malloc(sizeof(Node*) * 2);
	if (root == NULL) {
		result[0] = result[1] = NULL;
	} else {
			if (root->left == NULL) {
				result[0] = root;
			} else {
				Node** leftList = BST_To_DoublyLL(root->left);
				root->left = leftList[1];
				leftList[1]->right = root;
				result[0] = leftList[0];
			}
			if (root->right == NULL) {
				result[1] = root;
			} else {
				Node** rightList = BST_To_DoublyLL(root->right);
				root->right = rightList[0];
				rightList[0]->left = root;
				result[1] = rightList[1];
			}
		}
	return result;
}

struct TreeNode {

int val;

struct TreeNode *left, *right, *parent;

} *root;

typedef struct TreeNode Node;

Node** BST_To_DoublyLL2(Node* root) {

Node** result = (Node **) malloc(sizeof(Node*) * 2);

if (root == NULL) {

result[0] = result[1] = NULL;

} else {

if (root->left == NULL) {

result[0] = root;

} else {

Node** leftList = BST_To_DoublyLL(root->left);

root->left = leftList[1];

leftList[1]->right = root;

result[0] = leftList[0];

}

if (root->right == NULL) {

result[1] = root;

} else {

Node** rightList = BST_To_DoublyLL(root->right);

root->right = rightList[0];

rightList[0]->left = root;

result[1] = rightList[1];

}

return result;

}

Prateek Caire said on February 25, 2013

Simple inorder will also solve the problem
v = previously visited node
h = head of doubly linked list

v = null
T(n)
	if(n == null)
		return
	T(n->l)
	if(v == null)
		h = n
	else
		v->r = n
		n->l = v
		v = n
	T(n->r)

v = null

T(n)

if(n == null)

return

T(n->l)

if(v == null)

h = n

else

v->r = n

n->l = v

v = n

T(n->r)

komal said on May 15, 2013
Where are u filling v before de ref v->r. in the recursion.
VA:F [1.9.22_1171]
0
Reply

komal said on May 15, 2013
The code is precise. But, can u take a small example to explain it.
VA:F [1.9.22_1171]
0
Reply

2 trackbacks

Algorithm 3: Convert BST to Double Linked List | terribyte
on September 23, 2012
Convert Binary Search Tree (BST) to Sorted Doubly-Linked List | This is how Cheng grows up
on October 8, 2012