Javascript: algorithm to convert Binary search tree to doubly linked list

Question

I am trying to write the algorithm to convert a BST to a doubly linked list. This is what I have so far. Below is the code:

function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
}

function BinaryTree() {
    this.root = null;
}
 
BinaryTree.prototype.push = function(val) {
    var root = this.root;
    
    if(!root) {
        this.root = new TreeNode(val);
        return;
    }
    
    var currentNode = root;
    var newNode = new TreeNode(val);
    
    while(currentNode) {
        if (val < currentNode.val) {
        	if(!currentNode.left) {
            currentNode.left = newNode;
            break;
          } else {
              currentNode = currentNode.left;
          }
        } else if(val > currentNode.val) {
        	if(!currentNode.right) {
            currentNode.right = newNode;
            break;
          } else {
              currentNode = currentNode.right;
          }
        }
    }
}
var bt = new BinaryTree();
bt.push(4);
bt.push(2);
bt.push(5);
bt.push(1);
bt.push(3);
//console.log(bt);
//var node = bt.root;
function Node(node) {
  //this.data = value;
  //this.previous = this.next = null;
  var head = null;
  var tail = null;
  var prev = null;
  console.log(bstToLL(node, head, prev, tail));
}


//function DoublyLinkedList() {
//  this.head = null;
//  this.prev = null;
//  this.tail = null;
//}

function bstToLL(node, head, prev, tail) {
	if (node === null) {
  	return;
  }
  
  bstToLL(node.left, head, prev, tail);
  if (head === null) {
  	head = node;
    //console.log(head)
  }
  if (prev === null) {
  	prev = node;
    //console.log(prev)
  } else {
  	//console.log(node);
    //console.log(prev);
    node.left = prev;
    prev.right = node;
  }
  prev = node
  bstToLL(node.right, head, prev, tail);
  if(node.right === null) {
  	tail = node;
  }
  return head;
}

Node(bt.root);

The code works, but I don't think it is getting the right result. The binary tree looks like-

When I return the head from the bstToLL() method, I get an object with val 4 pointing to right child 5 and left child 2 and so on and so forth.

If you run the code, and check the debugger you will see the head object.

Can someone please guide me if I am doing this the right way, and how to fix the result?

Please include all the relevant code in the question itself. The link is not guaranteed to still work in the future — hugomg

csander csander · Accepted Answer · 2016-08-18T01:55:15

Here is some code which converts a binary tree into a LinkedList. It will log 1, 2, 3, 4, and 5, in order:

function TreeNode(left, value, right) {
  this.left = left;
  this.value = value;
  this.right = right;
}

function ListNode(prev, value, next) {
  this.prev = prev;
  this.value = value;
  this.next = next;
}

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 tree = new TreeNode(
  new TreeNode(
    new TreeNode(null, 1, null),
    2,
    new TreeNode(null, 3, null)
  ),
  4,
  new TreeNode(null, 5, null)
);
var linkedList = bstToLL(tree);
for (var node = linkedList.head; node; node = node.next) console.log(node.value);

Javascript: algorithm to convert Binary search tree to doubly linked list

1 Answers