Problem:
A Binary Search Tree can be mapped to a sorted Circular Doubly-Linked List.In a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
The left and right pointers in a binary search tree are mapped to the predecessor and successor pointers in a doubly-linked list.
Write a function to do the transformation in place, the function takes the root node of the tree as input and returns the pointer to the smallest element of the linked list.
For example,
Given binary search tree
5
/ \
3 8
/ \ \
2 4 9
the circular double linked list is:
2 <-> 3 <-> 4 <-> 5 <-> 8 <-> 9 <-> 2
return the pointer to node 2 in the linked list
Solution:
The requirement of in place conversion leave us no other choice but convert it during in-order traversal of the binary search tree. We first handle left node, then current node, then right node.
At the time we deal with current node, we should already have already converted the left subtree. The last node of the linked list is all we need to add the current node. After we added the current node, we need to pass the last node of the new linked list to the right sub tree.
If we pass the last node of the linked list to the in-order traversal function as a parameter, the recursive call to left subtree and right subtree won't be symmetric. At the current node, when deal with the left subtree, we don't know what node to pass in; when deal with the right subtree, we can pass in the current node as the last node of the linked list.
To deal with the above problem, we can store the last node as a global variable. At current node, we don't have to pass in anything, and when the recursive call for the left node finishes, the last node of the linked list is updated. The same applies when deal with the right node.
If we don't have to create a circular double linked list, we don't have to store the smallest node, however, this problem asked for it. So we need to store it. The way to store it is to walk to the left most tree node. This point is where we update the first node of the circular double linked list, it is also where our recursive calls start to return.
import java.util.*;
class Solution {
LNode first;
LNode last;
public static void main(String...args) {
Node root = new Node(5, new Node(3, new Node(2), new Node(4)), new Node(8, null, new Node(9)));
Solution s = new Solution();
s.transform(root);
s.last.next = s.first;
s.first.pre = s.last;
LNode cur = s.first;
while(cur.next != s.first) {
System.out.print(cur.val + "<->");
cur = cur.next;
}
System.out.print(cur.next.val);
}
/*
3
/ \
2 4
3 2<->3 first=2 last=3
2 first=2 last=2 4 2<->3<->4 first=2 last=4
null null null
*/
private void transform(Node root) {//
if(root == null)
return;
//move to left most node
transform(root.left);
LNode cur = new LNode(root.val, null, null);
if(first == null) {
first = cur;
last = cur;
return;
}
last.next = cur;
cur.pre = last;
last = cur;
transform(root.right);
}
private static class Node {
Node left;
Node right;
int val;
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
private static class LNode {
int val;
LNode pre;
LNode next;
public LNode(int val, LNode pre, LNode next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}
}
class Solution {
LNode first;
LNode last;
public static void main(String...args) {
Node root = new Node(5, new Node(3, new Node(2), new Node(4)), new Node(8, null, new Node(9)));
Solution s = new Solution();
s.transform(root);
s.last.next = s.first;
s.first.pre = s.last;
LNode cur = s.first;
while(cur.next != s.first) {
System.out.print(cur.val + "<->");
cur = cur.next;
}
System.out.print(cur.next.val);
}
/*
3
/ \
2 4
3 2<->3 first=2 last=3
2 first=2 last=2 4 2<->3<->4 first=2 last=4
null null null
*/
private void transform(Node root) {//
if(root == null)
return;
//move to left most node
transform(root.left);
LNode cur = new LNode(root.val, null, null);
if(first == null) {
first = cur;
last = cur;
return;
}
last.next = cur;
cur.pre = last;
last = cur;
transform(root.right);
}
private static class Node {
Node left;
Node right;
int val;
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
private static class LNode {
int val;
LNode pre;
LNode next;
public LNode(int val, LNode pre, LNode next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}
}
The time complexity is O(N) we need to deal with each one of the tree node, the space complexity is O(N), the double linked list size is proportional to the total number of tree node.
