Create Height Balanced BST from Sorted Linkedlist

By -

A height balanced search tree is the one in which the difference of height of the left subtree and height of the right subtree is not more than one for each node.

Height of a tree node - Length of the longest path from the node to the leaf node. The height of a tree is the height of its root node and the height of a leaf node is 0.

Check this article - Calculate the height of a binary tree

Now before creating a height balanced search tree let's understand why do we need a height balanced BST ?   

We know that a Binary Search Tree (BST) is a binary tree in which for each node its left child node is less than the node and right child node is greater than the node itself.
This property of the BST makes it suitable for search operations because while searching for a key during tree traversal, on each node we can eliminate the traversal of one entire subtree of the node (left subtree or right subtree) based on the value of search key.
For example let's try searching the key 30 in binary search tree given below -


Fig 1.0

Starting from root node (10) we will keep comparing the search key with node key and move to the node's right subtree if search key is greater than the key and move to the left subtree if the search key is less than the node key until search key is not found. Thus referring to the diagram above we will follow path (10 -> 40 -> 30) and find the search key eliminating the paths to the nodes with cross sign and their subtrees.
Now if we insert the elements in the binary search tree in ascending or descending order we will end up creating a binary search tree having all the nodes at the right only or left only position of each node starting from the root. Refer the figure of BST given below created by inserting the keys in ascending order. (eg. - 1, 5, 7, 10)

Fig 2.0

Above BST ((Fig 2.0)) is a valid binary search tree but it defeats the whole purpose of binary search tree because it is nothing more than a linked list. If we try to search the key 10 in this tree we will have to visit all its node. Similarly if we create a BST inserting the keys of tree given in Fig 1.0 in ascending order we will end up having the similar structure with all its nodes (1->5->7->10->30->40->50).

To overcome this situation we try to keep our binary search tree balanced to take the advantage of binary search tree.

Now after we know the advantage of having a height binary search tree over a simple binary search tree lets come to our original topic

Creating a height balanced search tree from a sorted linked list  -

Explaination -
Lets assume we have a sorted linked list with elements - 1, 5, 7, 10, 30, 40, 50
Now to create a BST from it we will divide the list into two halves and find the middle node of the list, now this middle node becomes the root node of the tree with left side elements representing the left sub tree nodes and right side elements representing the right sub tree of the node. We will keep doing this recursively for the right and left sub lists also to find their root nodes (middle element) until we reach at a point where we do not left with any sub list to divide.

Implementation -For better understanding we have implemented our own custom linked list class also. 

package ds.tree;

import ds.linkedlist.CLinkedList;
import ds.tree.BStree.Node;

public class LinkedListToBalancedBST {
	
    
public static BStree listToBST(CLinkedList list) {
		int size = list.size();
		if(size <= 0)
			throw new RuntimeException("List must not be empty.");
		Node root = createBST(1, size, list);
		return new BStree(root);
	}
	
	private static Node createBST(int l, int r, CLinkedList list) {
		if(l > r)
			return null;
		
		int m = l + (r-l)/2;
		Node root = new Node(list.elementAtPos(m));
		root.left = createBST(l, m-1, list);
		root.right = createBST(m+1, r, list);
		return root;
		
	}

}
Binary Search Tree (BStree.java) 

package ds.tree;

public class BStree {

	private Node root;

	public Node getRoot() {
		return root;
	}

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}
	
	public BStree(Node root) {
		this.root = root;
	}

	static class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
		}
	}
	
	public void printInOrder() {
		inOrderRec(this.root);
	}
	
	private void inOrderRec(Node root){
		if(root == null)
			return;
		inOrderRec(root.left);
		System.out.print(root.data + " ");
		inOrderRec(root.right);
	}
}
Custom Linked List (CLinkedList.java) 

package ds.linkedlist;

public class CLinkedList {
	
	private LNode head;
	
	class LNode{
		private int data;
		private LNode next;
		
		public LNode (int data) {
			this.data = data;
		}
	}
	
	public void add(int data) {
		LNode nNode = new LNode(data);
		if(this.head == null)
			this.head = nNode;
		else {
			LNode cNode = this.head;
			
			while(cNode.next != null) {
				cNode = cNode.next;
			}
			cNode.next = nNode;
		}
	}
	
	public int size() {
		LNode cNode = this.head;
		int count = 0;
		while(cNode != null) {
			cNode = cNode.next;
			count++;
		}
		return count;
	}
	
	public int elementAtPos(int pos) {
		int i = 0;
		LNode cNode = this.head;
		
		while(cNode != null) {
			i++;
			if(i == pos)
				break;
			cNode = cNode.next;
			
		}
		if(i < pos)
			throw new RuntimeException("List does not have enough elements.");
		return cNode.data;
	}
	
	public void print() {
		LNode cNode = this.head;
		while(cNode != null) {
			System.out.print(cNode.data + " ");
			cNode = cNode.next;
		}
	}
}
Main Class (BtreeMain.java) 

package ds.tree;

import ds.linkedlist.CLinkedList;

public class BtreeMain {
	
	public static void main(String[] args) {
		CLinkedList list = new CLinkedList();
		list.add(1);
		list.add(5);
		list.add(7);
		list.add(10);
		list.add(30);
		list.add(40);
		list.add(50);
		
		System.out.println("Print Linkedlist - ");
		list.print();
		
		System.out.println("\nTree In-Order -");
		BStree bst = LinkedListToBalancedBST.listToBST(list);
		bst.printInOrder();
	}
}
Output - 

Print Linkedlist - 
1 5 7 10 30 40 50 
Tree In-Order -
1 5 7 10 30 40 50
LinkedListToBalancedBST class has method listToBST(CLinkedList list) which takes linked list (sorted) and convert it into binary search tree. BtreeMain class above has a main method which creas a linkedlist which is sorted in ascending order and then converts it into a binary search tree (BStree). We know that In-Order traversal prints the binary search tree in ascending order so if our implementation is correct then In-Order traversal of our BST and linked list traversal should print the values in same order. We can confirm it from the output above that is printed with linked list traversal and In-Order traversal of output binary search tree.
Our implementation would have been even better if we used List instead of Linkedlist because it would have given us the middle element right away using the index instead of traversing the linkedlist.
Similarly we can create the BST from Linkedlist arranged in descending order, we just have to swap the right and left node pointer in above implementation.
Time complexity of this method is O(nLogn) where n is the number of Linkedlist nodes. In our upcoming articles we will see how we can write this implementation using different approach also how we can check whether an existing binary search tree is height balanced or not.

Comments

Post a Comment

Popular posts from this blog

Spring-Boot externalize logback configuration file (logback-spring.xml)

By -
Many times there is a need to externalize the logging configuration file in spring boot, so that without making any code level/ jar level changes we can easily change the logging configuration. For example If we deliver any spring boot application as a jar we dont want the logging file name to be hardcoded and to be present on any specific location, so If we have an opportunity to change the logging configuration file we can easily set the logging file location or name. Or take another example where we want to change the logging level or add logger for a new package we can easily do it if logging configuration file is externalized. Lets see how we can externalize logback loggin configuration file - Spring boot by default uses logback for logging and If we don't provide any configuration file It uses default configuration and prints logs in console. So if we want to make changes to the logback configuration we will have to create a logbacl configuration file. Follow below steps ...
Read more

Reverse LinkedList in K nodes group - Data Structure Linked List

By -
Image
I this problem we have to reverse the nodes of the Linkedlist k at a time and leave the remaining nodes if number of nodes is not a multiple of k. For example If we have a LinkedList having 11 nodes and we are asked to reverse it for k=3 nodes at a time, we will reverse first 3 elements then next 3 elements and then again next 3 elements and leave the last 2 elements as it is. Check below diagram to understand the example - Approach : First we will find the size of the LinkedList and divide it by k to know the number of groups which needs to be reversed. We will write a recursive method which will reverse the group of k nodes and return the last node of the reversed group. We will call this recursive function for all the groups which needs to be revesed. In above example list size is 11 and value of k is 3 so we will get total 11/3 3 groups which needs to be reversed leaving the last 2 ekements unchanged. To revese the pointed of a node we will use simple iterative approach ...
Read more

Finding Height Of A Binary Tree

By -
Image
Height of a Binary tree is the length of the path form its root node to its farthest leaf node or we can say the longest path from root node to any of the leaf node (here path means the link between two nodes). For example - height of the binary tree in the figure given below (Fig 1.0) is 3. As we can see that this tree has two leaf nodes 3 and 12 but node leaf 3 is the farthest from the root and length of the path between 10 (root node) and 3 (farthest leaf node) is 3 hence height of the tree is 3. From above example comes our algorithm to calculate the height of the tree, we will calculate the height of the left and right subtree of each node recursively and consider the height of the tree including the root node - adding one to the greater of the two heights (left and right subtree heights). Fig 1.0 Implementation - In below code we have implementaed a custom BST with a public method getHeight() which internaly calls another private method getHeight() passing root of the tree ...
Read more

Spring Cloud - Configuration Server with Git Integration

By -
Spring Cloud is a Spring module which provides the features to make the development of distributed cloud-based applications simple and quick. Spring cloud configuration server is also one of the features which help us in the configuration management of distributed applications. In this article, we will discuss how spring cloud configuration can be used to externalize and manage the configurations of different distributed applications for different environments from a single place. We will be using a git repository as a configuration store which is considered an ideal choice. 1. Setting up Configuration Server - We will create a simple spring boot application which with the help of some dependencies will work as our configuration server serving configuration to our client application using a git versioned configuration store. 1.1 Create a spring boot application with below-required dependencies and import it to your IDE.    <dependency> <groupId>org.springfra...
Read more