Sorted List to complete BST

Contents:

1. Constructing the binary tree
2. Ensuring a complete binary tree
3. Example implementation of the algorithm
4. Links
5. See also

Constructing the binary tree

• The first right child of any node is always a leave. This is very important for the next section. Node 1 is actually the first right child of an imaginary root node which carries the entire constructed tree.
• A perfect binary sub-tree has its root node carried by a node one level higher: 4 carries 2, 2 carries 1, and 1 carries the null node. Also the imaginary root carries 4 (it is at three levels higher than 1).
• The levels can be numbered: a null node is at level zero, a leave (such as 1) is at level one, 2 is at level two, 4 is at level three, the imaginary root is at level four (= 1+3 = 1 + the number of bits of n).
• During construction, when a sub-tree is full the algorithm climbs up the tree and stops when the difference in levels is greater than one, after which it inserts a new node.

1. Create the imaginary root node, and set its level number to 1 + the number of bits of n.
2. Currently the root node is also the current node. The current node is the node we currently lie on.
3. Get the next element in the list and create a new node with it.
   
   
4. Climb up the tree as long as the level number of the current node is one greater than that of its child node. This child is always the right child, since the current node is always on the right of its parent. No right child means a null node whose level number is zero.
   
   
5. Set the level number of the new node to be one greater than that of the old right child. Then set the left child of the new node to be the old right child of the current node. Finally set the new right child of the current node to be the new node (also set the parent of the new node). If there is nothing to set then nothing is set.
   
   
6. Set the 'current node' to be the new node.
7. Repeat steps 3, 4, 5 and 6 till there is no element left.

Ensuring a complete binary tree

Example implementation of the algorithm

#include <stdio.h>
#include <malloc.h>

typedef struct _Node
{
	int data;
	struct _Node *next; // for the Sorted Linked-List
	struct _Node *parent, *left, *right; // for the BST
} Node;


void print_tree (const Node* node, int indent)
{
	int i;
	if(node==NULL) return;
	print_tree (node->right, indent+4);     // print right sub-tree
	for(i=0; i<indent; i++) putchar(' ');   // print indent spaces
	printf("%d\r\n", node->data);           // print current node
	print_tree (node->left, indent+4);      // print left sub-tree
}


Node* sorted_list_to_complete_binary_search_tree (Node* list)
{
	int i, n;                       // needed storage size is k=log(n)
	char h;                         // needed storage size is log(k)
	char stack[32];                 // needed storage size is k*log(k)
	int leaves;                     // = number of leaves remaining
	Node *current;                  // = pointer to current node
	Node root = {0};                // = root node that holds the tree
	if(list==NULL) return NULL;

	// get the length 'n' of the list
	for(n=0, current=list; current!=NULL; current = current->next, n++);
	for(h=0, i=n+1; i>1; i=i>>1, h++); // get h = floor(log2(n+1))
	leaves = n+1 - (1<<h);             // get number of leaves = n+1 - 2^h
	printf("n = %d , leaves = %d\r\n", n, leaves);

	// prepare to start
	if(leaves!=0) h++;      // Get h = number of bits of n (by improvising!)
	stack[0] = h+1;         // Set initial content of stack: the root node
	stack[1] = 0;           // is at level h+1, the null node is at level 0.
	h = 0;                  // Set 'h' to the beginning of stack.
	current = &root;        // At first, the current node is the root node.

	// start algorithm
	for( ; list != NULL; list = list->next) // 'list' is the 'new node'
	{
		while(stack[h] == stack[h+1]+1)     // While the tree-level ordering
		{ h--; current = current->parent; } // is fine, climb up the tree.
		stack[++h] = stack[h]+1;     // Increment 'h' then set the tree-level of
		stack[h+1] = 0;              // the new node. Set null node's level to 0.

		list->parent = current;          // Insert the new node in the tree:
		list->right = NULL;              // set sub-right child to null,
		list->left = current->right;     // set old right child as sub-left child,
		current->right = list;           // set new right child to be the new node,
		current = list;                  // set 'current' to be the new node,
		if(list->left != NULL)
			list->left->parent = list;   // set new parent of sub-left child.

		// Remove this 'else' part so to observe its important effect
		// of ensuring that the tree is a 'complete' binary tree.
		else if(leaves!=0)
		{
			leaves--;       // the new node is a leave node, so count it
			if(leaves==0)   // if no more leaves then the null level will change
			{
				for(i=0; i<=h; i++) stack[i]--; // step all levels down, old leave
				h--; current = current->parent; // level now becomes new null level
			}
		}
		//print_tree(&root, 0);
	}
	// return the correct root of the tree
	root.right->parent = NULL;
	return root.right;
}


int main ()
{
	int i, n=0;
	Node *list=NULL;
	Node *tree, *node;

	while(1)
	{
		// get length 'n' of list
		printf("Enter n (or 0 for next n): ");
		scanf("%d", &i);
		if(i<=0) n += 1;
		else n = i;

		// re-allocate memory
		list = (Node*) realloc (list, n*sizeof(Node));

		// construct linked-list
		for(i=0; i < n-1; i++)
			list[i].next = &list[i+1];
		list[n-1].next = NULL;

		// set list data (such that it is a sorted list)
		for(i=1, node=list; node!=NULL; node = node->next, i++)
			node->data = i;

		// apply algorithm
		tree = sorted_list_to_complete_binary_search_tree (list);

		// print result
		printf("--------------------------------------\r\n");
		print_tree(tree, 0);
		printf("--------------------------------------\r\n");
	}
	// free allocated memory...?
	free(list);
	return 0;
}

Links

1. http://en.wikipedia.org/wiki/Binary_search_tree
2. https://en.wikipedia.org/wiki/Tree_traversal
3. https://ece.uwaterloo.ca/~cmoreno/ece250/4.05.PerfectBinaryTrees.pdf
4. http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf
5. Algorithms - Expression parsing algorithm

See also

• Math expression parsing algorithm
• Generate nth palindromic number
• Find maximum bipartite matching