Skip to content

Commit 09ddf68

Browse files
xiaoningningxiaoningning
committed
update in place bst to double linked list
1 parent 85934d3 commit 09ddf68

2 files changed

Lines changed: 184 additions & 109 deletions

File tree

‎PuzzleCoding/src/BSTtoDLL.java‎

Lines changed: 143 additions & 109 deletions
Original file line numberDiff line numberDiff line change
@@ -1,109 +1,143 @@
1-
import java.util.ArrayList;
2-
import java.util.Stack;
3-
4-
/**
5-
* Convert a BST to a sorted circular doubly-linked list in-place.
6-
* Think of the left and right pointers as synonymous to the previous
7-
* and next pointers in a doubly-linked list.
8-
* <p/>
9-
* This is a modified in-order traversal adapted to this problem.
10-
* prev (init to NULL) is used to keep track of previously traversed node.
11-
* head pointer is updated with the list's head as recursion ends.
12-
* <p/>
13-
* do it in place. time complexity: O(n)
14-
*/
15-
public class BSTtoDLL {
16-
public static void main(String[] args) {
17-
Node root = new Node(10);
18-
Node node5 = new Node(5);
19-
Node node15 = new Node(15);
20-
Node node6 = new Node(6);
21-
Node node20 = new Node(20);
22-
Node node3 = new Node(3);
23-
Node node12 = new Node(12);
24-
25-
root.insert(node5);
26-
root.insert(node6);
27-
root.insert(node15);
28-
root.insert(node20);
29-
root.insert(node3);
30-
root.insert(node12);
31-
32-
ArrayList<Node> dll = bstToDLL(root);
33-
printDll(dll);
34-
35-
bstToDll1(root);
36-
37-
System.out.print(tail.value);
38-
39-
}
40-
41-
42-
public static void printDll(ArrayList<Node> dll) {
43-
if (dll.size() != 0) {
44-
for (Node n : dll) {
45-
System.out.print(n.value + " ");
46-
}
47-
}
48-
System.out.println();
49-
}
50-
51-
// not in place
52-
public static ArrayList<Node> bstToDLL(Node node) {
53-
if (node == null)
54-
return null;
55-
56-
Stack<Node> stack = new Stack<Node>();
57-
ArrayList<Node> dll = new ArrayList<Node>();
58-
Node current = node;
59-
boolean done = false;
60-
while (!done) {
61-
if (current != null) {
62-
stack.push(current);
63-
current = current.left;
64-
} else {
65-
if (stack.isEmpty()) {
66-
done = true;
67-
} else {
68-
current = stack.pop();
69-
dll.add(current);
70-
current = current.right;
71-
}
72-
}
73-
}
74-
return dll;
75-
}
76-
77-
static Node prev, tail;
78-
79-
public static void bstToDll1(Node p) {
80-
if (p == null)
81-
return;
82-
83-
bstToDll1(p.left);
84-
p.left = prev;
85-
// current node (smallest element) is head of
86-
// the list if previous node is not available
87-
if (prev == null){
88-
tail = p;
89-
}
90-
else{
91-
92-
prev.right = p;
93-
}
94-
95-
// as soon as the recursion ends, the head's left pointer
96-
// points to the last node, and the last node's right pointer
97-
// points to the head pointer.
98-
99-
Node rightNode = p.right;
100-
tail.left = p;
101-
p.right = tail;
102-
prev = p;
103-
104-
bstToDll1(rightNode);
105-
106-
}
107-
108-
109-
}
1+
import java.util.ArrayList;
2+
import java.util.Stack;
3+
4+
/**
5+
* Convert a BST to a sorted circular doubly-linked list in-place. Think of the
6+
* left and right pointers as synonymous to the previous and next pointers in a
7+
* doubly-linked list.
8+
* <p/>
9+
* This is a modified in-order traversal adapted to this problem. prev (init to
10+
* NULL) is used to keep track of previously traversed node. head pointer is
11+
* updated with the list's head as recursion ends.
12+
* <p/>
13+
* do it in place. time complexity: O(n)
14+
*/
15+
public class BSTtoDLL {
16+
public static void main(String[] args) {
17+
Node root = new Node(10);
18+
Node node5 = new Node(5);
19+
Node node15 = new Node(15);
20+
Node node6 = new Node(6);
21+
Node node20 = new Node(20);
22+
Node node3 = new Node(3);
23+
Node node12 = new Node(12);
24+
Node node14 = new Node(14);
25+
26+
27+
root.insert(node5);
28+
root.insert(node6);
29+
root.insert(node15);
30+
root.insert(node20);
31+
root.insert(node3);
32+
root.insert(node12);
33+
root.insert(node14);
34+
35+
ArrayList<Node> dll = bstToDLL(root);
36+
printDll(dll);
37+
38+
bstToDllinPlace(root);
39+
40+
printDll(head);
41+
42+
}
43+
44+
public static void printDll(Node n) {
45+
if (n == null) {
46+
System.out.println("null");
47+
} else {
48+
int s = n.value;
49+
System.out.print(n.value + " ");
50+
n = n.right;
51+
while (n.value != s) {
52+
System.out.print(n.value + " ");
53+
n = n.right;
54+
}
55+
}
56+
System.out.println();
57+
}
58+
59+
public static void printDll(ArrayList<Node> dll) {
60+
if (dll.size() != 0) {
61+
for (Node n : dll) {
62+
System.out.print(n.value + " ");
63+
}
64+
}
65+
System.out.println();
66+
}
67+
68+
// not in place
69+
public static ArrayList<Node> bstToDLL(Node node) {
70+
if (node == null)
71+
return null;
72+
73+
Stack<Node> stack = new Stack<Node>();
74+
ArrayList<Node> dll = new ArrayList<Node>();
75+
Node current = node;
76+
boolean done = false;
77+
while (!done) {
78+
if (current != null) {
79+
stack.push(current);
80+
current = current.left;
81+
} else {
82+
if (stack.isEmpty()) {
83+
done = true;
84+
} else {
85+
current = stack.pop();
86+
dll.add(current);
87+
current = current.right;
88+
}
89+
}
90+
}
91+
return dll;
92+
}
93+
94+
static Node prev, head;
95+
96+
public static void bstToDllinPlace(Node p) {
97+
if (p == null)
98+
return;
99+
100+
bstToDllinPlace(p.left);
101+
p.left = prev;
102+
// current node (smallest element) is head of
103+
// the list if previous node is not available
104+
if (prev == null) {
105+
head = p;
106+
} else {
107+
108+
prev.right = p;
109+
}
110+
System.out.print("parent: " + p.value + " prev: ");
111+
nodeToString(prev);
112+
System.out.print(" head: ");
113+
nodeToString(head);
114+
115+
// as soon as the recursion ends, the head's left pointer
116+
// points to the last node, and the last node's right pointer
117+
// points to the head pointer.
118+
119+
Node rightNode = p.right;
120+
head.left = p;
121+
p.right = head;
122+
prev = p;
123+
124+
bstToDllinPlace(rightNode);
125+
126+
System.out.print("parent: " + p.value + " prev: ");
127+
nodeToString(prev);
128+
System.out.print(" head: ");
129+
nodeToString(head);
130+
131+
}
132+
133+
public static void nodeToString(Node n) {
134+
if (n == null) {
135+
System.out.println("null");
136+
137+
} else {
138+
System.out.println(n.value);
139+
}
140+
141+
}
142+
143+
}

‎PuzzleCoding/src/Node.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/**
2+
* a node class for tree
3+
*/
4+
public class Node {
5+
public int value;
6+
public Node left;
7+
public Node right;
8+
9+
public Node(int v){
10+
value = v;
11+
left = null;
12+
right = null;
13+
14+
}
15+
public boolean insert(Node n){
16+
if(n == null)
17+
return false;
18+
if(value >= n.value){
19+
if(left == null)
20+
left = n;
21+
else
22+
left.insert(n);
23+
}else {
24+
if(right == null)
25+
right = n;
26+
else
27+
right.insert(n);
28+
}
29+
return true;
30+
}
31+
public int size(){
32+
int size = 0;
33+
if(left != null){
34+
size += left.size();
35+
}
36+
if(right != null){
37+
size += right.size();
38+
}
39+
return size + 1;
40+
}
41+
}

0 commit comments

Comments
 (0)