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.

// Tree.java

public class Tree {

private static class Node {

int data;

Node left;

Node right;

/** Node constructor that adds the data

*

* @param newData is the data to be inserted

*/

Node (int newData) {

data = newData;

left = null;

right = null;

}

}

private Node root;

Tree () {

root = null;

}

/** insert a new data into the tree incapsulation method

*

* @param newData is the data to be inserted

*/

public void insert (int newData) {

root = insert(root, newData);

}

/** insert data actual implementation method

* in this version of binary tree, the data will be appended

* to the right tree if it is equal

*

* @param node is the current node

* @param newData is the data to be inserted

* @return the node in which newData is inserted

*/

private Node insert (Node node, int newData) {

if (node == null)

node = new Node (newData);

else if (newData < node.data)

node.left = insert (node.left, newData);

else // if (newData >= node.data)

node.right = insert (node.right, newData);

return node;

}

/** convert a binary tree data structure into a sorted

* doubly linked list structure

* this encapsulates the actual implementation and

* takes care of the last linking process

*

* the head of the doubly linked list will be saved in root

*/

public void convertTree() {

Node temp = root;

root = null;

temp = convertTree(temp);

// root holds the latest node

linkNodes (root, temp);

root = temp;

}

/** actual implementation method for the converting

* algorithm by recursion

* will link the current node and the previous node

*

* @param node is the current node

* @return the head of the doubly linked list

*/

private Node convertTree(Node node) {

if (node == null)

return null;

Node ret = convertTree(node.left);

if (root == null)

// this is the first node

ret = node;

else

// root holds the previous node

linkNodes (root, node);

root = node;

convertTree(node.right);

return ret;

}

/** a simple helper method to link two nodes into a list

*

* @param a is the smaller list element

* @param b is the very next list element

*/

private void linkNodes (Node a, Node b) {

a.right = b;

b.left = a;

}

}

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.

## No comments:

## Post a Comment