## Tuesday, November 17, 2015

### Efficient Binary Tree to Sorted Doubly Linked List Conversion Recursive Algorithm

I would like to share my own algorithm for converting a binary tree data structure to a sorted doubly linked list using recursion. I believe this is a very easy and efficient way to achieve the goal.

The basic idea is this: I will recursively enter into nodes in the increasing order. For each node, I will double-link its node and the previous node; the previous node is saved in the root field. After linking, the method will save its current node into the root field. This will take care of the doubly-linked list except for the first and the last nodes. For the last set of linking process, I make sure to work it out in the encapsulation function.

The reason I am saving the current (or previous) node in the root field is because Java does not have a static local variable within a method. I could, of course, create a new field for this purpose, but I did not want to do so just for this functionality. In order to use only the resources that are available to me, I decided to temporarily make use of the root field as a local static variable.

In order to determine whether I have reached the starting node (i.e., the node with the smallest data value), I check whether the root field is null, because root is set to null in the encapsulation method as an initialization. Once I reach the starting node, I set the root field to point to the current (or previous depending on the context) node.

This algorithm, I believe, is fairly fast because there is no waste of node assignment here in the linking process; that is, for every pair of nodes, there is only one set of linking assignments (i.e., 2) needed, so exactly 2N node assignments are required for a binary tree of size N.