Question

Consider a simple node-like data structure called BiNode, which has pointers to two other nodes.

public class BiNode {
    public BiNode node1, node2;
    public int data;
}

The data structure BiNode could be used to represent both a binary tree (where node1 is the left node and node2 is the right node) or a doubly linked list (where node1 is the previous node and node2 is the next node). Implement a method to convert a binary search tree (implemented with BiNode) into a doubly linked list. The values should be kept in order and the operation should be performed in place (that is, on the original data structure).

Solution

At another post [LeetCode Plus] Convert BST to Circular DLL, we already discussed 2 approaches:

  1. in-order traversal approach
  2. divide and conquer approach

First approach isn’t intuitive. We will further discuss D&C approach here.

The key of the solution is how we return both HEAD and TAIL. The book suggests 3 ways:

  1. Build a data structure to store both head and tail
  2. Just return head, and retrieve tail by traversing thru - bad time complexity O(n^2)
  3. Use circular linked-list! Time O(n).

I wrote the code for 1st and 2nd approach. And 3rd is already covered in previous post.

  • You need to understand why we need the list to be circular.

Code

Approach 1

public static BiNode convert(BiNode root) {
	BiNodePair res = helper(root);
	return res.leftMost;
}

private static BiNodePair helper(BiNode node) {
	if (node == null) {
		return null;
	}
	BiNodePair res = new BiNodePair(node, node);
	if (node.node1 != null) {
		BiNodePair leftRes = helper(node.node1);
		res.leftMost = leftRes.leftMost;
		leftRes.rightMost.node2 = node;
		node.node1 = leftRes.rightMost;
	}
	if (node.node2 != null) {
		BiNodePair rightRes = helper(node.node2);
		res.rightMost = rightRes.rightMost;
		rightRes.leftMost.node1 = node;
		node.node2 = rightRes.leftMost;
	}
	return res;
}

static class BiNodePair {
	BiNode leftMost;
	BiNode rightMost;

	public BiNodePair(BiNode node1, BiNode node2) {
		leftMost = node1;
		rightMost = node2;
	}
}

Approach 2

public static BiNode convert(BiNode root) {
	if (root == null) {
		return null;
	}
	return helper(root);
}

private static BiNode helper(BiNode node) {
	// node is not null
	BiNode newHead = node;
	// do left part
	if (node.node1 != null) {
		newHead = helper(node.node1);
		BiNode leftTail = getListTail(newHead);
		leftTail.node2 = node;
		node.node1 = leftTail;
	}
	// do right part
	if (node.node2 != null) {
		BiNode rightHead = helper(node.node2);
		node.node2 = rightHead;
		rightHead.node1 = node;
	}
	return newHead;
}

private static BiNode getListTail(BiNode head) {
	// head is not null
	while (head.node2 != null) {
		head = head.node2;
	}
	return head;
}