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.

	// 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;
	}
	}

view raw Tree.java hosted with ❤ by GitHub

// 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.

Binary Tree Data Structure in Java for C/C++ Developers

Binary tree data structure is one of the fundamental data structures that appears in the beginning of the computer science course. In this post, I will explain a very simple binary tree class implementation in Java. As someone who has come from C/C++ language, it was a wonder for me how Java implements binary tree data structure, for Java supposedly does not have the concept of a pointer. However after studying Java for some time, it appears to me that Java actually does make use of pointers extensively. All the primitive data types, such as int, char, boolean are passed by its values while all objects are passed by reference. It turns out that Java's implementation makes it easier for programmers to write code at the expense of perhaps sacrificing the speed compared to C/C++; with C/C++ programmers have the maximum capability to manipulate every single details of the code and optimize for speed boost whereas with Java programmers are stuck with Java's built-in optimization.

In any case, here is the Java code for implementation of the tree class

	public class Tree {
	private static class Node {
	int data;
	Node left;
	Node right;
	/** Node constructor that adds the data
	*
	* @param data to be inserted
	*/
	Node (int data) {
	data = data;
	left = null;
	right = null;
	}
	}
	private Node root;
	Tree () {
	root = null;
	}
	/** insert a new data into the tree incapsulation method
	*
	* @param data to be inserted
	*/
	public void insert (int data) {
	root = insert(root, data);
	}
	/** 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 data to be inserted
	* @return the node in which data is inserted
	*/
	private Node insert (Node node, int data) {
	if (node == null)
	node = new Node (data);
	else if (data < node.data)
	node.left = insert (node.left, data);
	else // if (data >= node.data)
	node.right = insert (node.right, data);
	return node;
	}
	/** lookup data incapsulation method
	*
	* @param data to be searched within the tree
	* @return the total number of nodes that contain the data
	*/
	public int lookup (int data) {
	return lookup (root, data);
	}
	/** lookup data actual implementation method
	*
	* @param node is the current node
	* @param data is the data to be searched
	* @return the number of nodes containing the data in the
	* subtree starting from node
	*/
	private int lookup (Node node, int data) {
	if (node == null)
	return 0;
	else if (node.data == data)
	return lookup (node.right, data) + 1;
	else if (data < node.data)
	return lookup (node.left, data);
	else
	return lookup (node.right, data);
	}
	}

view raw Tree.java hosted with ❤ by GitHub

// Tree.java

public class Tree {

private static class Node {

int data;

Node left;

Node right;

/** Node constructor that adds the data

* 

* @param data to be inserted

*/

Node (int data) {

data = data;

left = null;

right = null;

}

}

private Node root;

Tree () {

root = null;

}

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

* 

* @param data to be inserted

*/

public void insert (int data) {

root = insert(root, data);

}

/** 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 data to be inserted

* @return the node in which data is inserted

*/

private Node insert (Node node, int data) {

if (node == null)

node = new Node (data);

else if (data < node.data)

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

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

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

return node;

}

/** lookup data incapsulation method

* 

* @param data to be searched within the tree

* @return the total number of nodes that contain the data

*/

public int lookup (int data) {

return lookup (root, data);

}

/** lookup data actual implementation method

* 

* @param node is the current node

* @param data is the data to be searched

* @return the number of nodes containing the data in the 

  * subtree starting from node

*/

private int lookup (Node node, int data) {

if (node == null)

return 0;

else if (node.data == data)

return lookup (node.right, data) + 1;

else if (data < node.data) 

return lookup (node.left, data);

else 

return lookup (node.right, data);

}

}

Any experienced C++ programmers should immediately understand what the code is doing and what each method is doing. For actual implementation of the binary tree, below is the Main class that builds a tree from Tree.java

	// Main.java
	public class Main {
	/** main method
	*
	* @param args is the argument strings passed from the user
	*/
	public static void main(String[] args) {
	Tree binaryTree = new Tree();
	binaryTree.insert(2);
	binaryTree.insert(1);
	binaryTree.insert(-2);
	binaryTree.insert(1);
	System.out.println("lookup(1) = " + binaryTree.lookup(1));
	}
	}

view raw Main.java hosted with ❤ by GitHub

// Main.java

public class Main {

/** main method

* 

* @param args is the argument strings passed from the user

*/

public static void main(String[] args) {

Tree binaryTree = new Tree();

binaryTree.insert(2);

binaryTree.insert(1);

binaryTree.insert(-2);

binaryTree.insert(1);

System.out.println("lookup(1) = " + binaryTree.lookup(1));

  }

}

Short Circuit Expressions in C/C++ and Java

It was quite embarassing for me today. For more than 10 years since I started learning C language, I have not even heard of "short-circuit evaluation" until today. Today, I was studying a simple BinaryTree program in Java, and I encountered somewhat peculiar problem; I actually thought I found some sort of Java's fundamenetal error, but oh well. I was the culprit.

If you see a code below, what would you guess the output is?

	public class ShortCircuit {
	private static boolean funcReturningTrue () {
	System.out.println ("this function returns true");
	return true;
	}
	private static boolean funcReturningFalse () {
	System.out.println ("this function returns false");
	return false;
	}
	public static void main (String[] args) {
	if (funcReturningTrue() || funcReturningFalse())
	System.out.println ("eval 1 complete");
	if (funcReturningFalse() && funcReturningTrue())
	;
	else
	System.out.println ("eval 2 complete");
	boolean bool = (true) ? funcReturningTrue() : funcReturningFalse();
	System.out.println ("bool = " + bool);
	}
	}

view raw ShortCircuit.java hosted with ❤ by GitHub

public class ShortCircuit {
    private static boolean funcReturningTrue () {
        System.out.println ("this function returns true");
        return true;
    }
    private static boolean funcReturningFalse () {
        System.out.println ("this function returns false");
        return false;
    }
    
    public static void main (String[] args) {
        if (funcReturningTrue() || funcReturningFalse())
            System.out.println ("eval 1 complete");
            
        if (funcReturningFalse() && funcReturningTrue())
            ;
        else
            System.out.println ("eval 2 complete");
            
        boolean bool = (true) ? funcReturningTrue() : funcReturningFalse();
        System.out.println ("bool = " + bool);
    }
}

Well, I naively thought that both static methods inside if () evaluation would be called; I was wrong. It seems that there are some short-circuit implementation in order to save run time. For example, (true || bool) is evaluated to be true regardless of bool, so C/C++ and Java will not even evaluate bool. That is, only funcReturningTrue() will be called in the code above for the 1st if statement.

Similarly, (false && bool) is false regardless of bool, so again bool will not be evaluated. This corresponds to the 2nd if statement in the code above.

Lastly, the statement (condition) ? a : b will evaluate only a or b but not both depending on the condition. If one were to make sure that both conditions to be evaluated in the examples above, one should use | and & in place of || and &&.

Now, one can easily predict the output of the program above:
this function returns true
eval 1 complete
this function returns false
eval 2 complete
this function returns true
bool = true