Converting Binary Trees to Doubly Linked Lists for Fun & Profit

Matt Hinea
Sep 11, 2016 · 4 min read
function Node(data, left, right) { 
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.data;
}
function Node(value, left, right) {
this.value = value;
this.left = left;
this.right = right;
this.show = show;
}
function show() {
return this.value;
}
var root = new Node(10);

root.left = new Node(12);
root.left.left = new Node(25);
root.left.right = new Node(30);

root.right = new Node(15);
root.right.left = new Node(36);
function convertBinaryTreeToDLL(root, headingLeft) {
var leftChild = root.left;
var rightChild = root.right;
var inorderPredecessor;
if (headingLeft) {
inorderPredecessor = rightChild;
} else {
inorderPredecessor = leftChild;
};
if (leftChild && (leftChild.left || leftChild.right)) {
convertBinaryTreeToDLL(leftChild, true);
}
if (rightChild && (rightChild.left || rightChild.right)) {
convertBinaryTreeToDLL(rightChild, false);
}
var rootDLL;
if (noFurtherSubtrees(root)) {
rootDLL = new DLLNode(root.value);
if (leftChild) {
rootDLL.previous = new DLLNode(leftChild.value);
}
if (rightChild) {
rootDll.next = new DLLNode(rightChild.value);
}
}
return rootDLL}function noFurtherSubtrees(root) {
var leftChild = root.left;
var rightChild = root.right;
if (leftChild) {
if (leftChild.left || leftChild.right) return false;
}
if (rightChild) {
if (rightChild.left || rightChild.right) return false;
}
return true
}
function TreeNode(left, value, right) {
this.value = value;
this.left = left;
this.right = right;
}
function ListNode(prev, value, next) {
this.prev = prev;
this.value = value;
this.next = next;
}
var tree = new TreeNode(
new TreeNode(
new TreeNode(null, 25, null),
12,
new TreeNode(null, 30, null)
),
10,
new TreeNode(
new TreeNode(null, 36, null),
15,
null
)
);
function LinkedList(head, tail) {
if (tail === undefined) tail = head;
this.head = head;
this.tail = tail;
}
LinkedList.prototype.addToStart = function(list) {
this.head.prev = list.tail;
list.tail.next = this.head;
this.head = list.head;
}
LinkedList.prototype.addToEnd = function(list) {
this.tail.next = list.head;
list.head.prev = this.tail;
this.tail = list.tail;
};
function bstToLL(tree) {
var centerNode = new ListNode(null, tree.value, null);
var list = new LinkedList(centerNode);
if (tree.left) list.addToStart(bstToLL(tree.left));
if (tree.right) list.addToEnd(bstToLL(tree.right));
return list;
}
var linkedList = bstToLL(tree);
for (var node = linkedList.head; node; node = node.next) console.log(node.value);
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade