In this post, we will talk and learn about How to convert sorted LinkedList to a balanced binary search tree (BST).
Here I will talk about a couple of approaches:
The logic Used in this Program:
In this approach first, we find the middle element of LinkedList and make it root and do it recursively.
Time complexity: o(nlogn).
This solution usually follows a bottom-up approach rather than top-down.
- First, we find the length of LinkedList
- Afterward, we create the left subtree recursively using n/2 nodes.
- Then we will create the root node and connect the left subtree to the root node.
- Finally, we create the right subtree recursively and connect root to the right subtree.
Below Program is
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
package com.kkjavatutorials.util; /** * How to convert sorted Linked List to balanced Binary Search Tree(BST) ? * @author KK JavaTutorials */ public class LinkedList<T> { private Node<T> head; //This internal class represents Node in Linked List private static class Node<T>{ private T data; private Node<T> next; public Node(T data) { super(); this.data = data; this.next = null; } } /* * This internal class represents Node in BST */ private static class BinarySeachTree<T> { private T data; private BinarySeachTree<T> left; private BinarySeachTree<T> right; public BinarySeachTree (T value) { this.data = value; this.left = null; this.right = null; } } /** * This method returns size/length of Linked List * @return size of Linked List */ public int lengthOfLinkedList() { int length = 0; if(head == null) { return length; } Node<T> currentNode = head; while (currentNode != null) { length ++; currentNode = currentNode.next; } return length; } /** * This method insert a Node in Linked List * @param newNode has to insert in the List */ public void insert(Node<T> newNode) { if(head == null) { head = newNode; }else { Node<T> currentNode = head; while (currentNode.next != null) { currentNode = currentNode.next; } currentNode.next = newNode; } } /** * Method to traverse PreOrder of BST * @param rootNode */ public void preOrder(BinarySeachTree<T> rootNode) { if (rootNode == null) return; System.out.print(rootNode.data + " "); preOrder(rootNode.left); preOrder(rootNode.right); } /** * Method which converts Sorted Linked List to balanced * Binary Search Tree(BST) * @param lengthOfLinkedList number of nodes * @return constructed BST */ public BinarySeachTree<T> convertSortedLinkedListToBST(int lengthOfLinkedList) { //Base Case of recursion if (lengthOfLinkedList <= 0) return null; /* Recursively creating the left subtree of BST*/ BinarySeachTree<T> left = convertSortedLinkedListToBST(lengthOfLinkedList / 2); //Creating a root node BinarySeachTree<T> rootNode = new BinarySeachTree<T>(head.data); //Setting pointer to left subtree rootNode.left = left; head = head.next; /* Creating right subtree with remaining nodes*/ rootNode.right = convertSortedLinkedListToBST(lengthOfLinkedList - lengthOfLinkedList / 2 - 1); return rootNode; } /** * Method which traverse Linked List and display all data. */ public void displayLinkedList() { Node<T> currentNode = head; while(currentNode!= null) { System.out.print(currentNode.data+" "); currentNode = currentNode.next; } } public static void main(String[] args) { Node<Integer> node1 = new Node<Integer>(10); Node<Integer> node2 = new Node<Integer>(20); Node<Integer> node3 = new Node<Integer>(30); Node<Integer> node4 = new Node<Integer>(40); Node<Integer> node5 = new Node<Integer>(50); Node<Integer> node6 = new Node<Integer>(60); Node<Integer> node7 = new Node<Integer>(70); LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.insert(node1); linkedList.insert(node2); linkedList.insert(node3); linkedList.insert(node4); linkedList.insert(node5); linkedList.insert(node6); linkedList.insert(node7); System.out.println("Printing LinkedList::"); linkedList.displayLinkedList(); int lengthOfLinkedList = linkedList.lengthOfLinkedList(); BinarySeachTree<Integer> bst = linkedList.convertSortedLinkedListToBST(lengthOfLinkedList); System.out.println(); System.out.println("PreOrder traversal of binary search tree(BST) :"); linkedList.preOrder(bst); } } |
Output of this program:
Printing LinkedList::
10 20 30 40 50 60 70
PreOrder traversal of binary search tree(BST) :
40 20 10 30 60 50 70
You May Also Like:
- How to remove a given key from the Singly Linked List in Java ?
- How to remove a node from a Singly Linked List at a given position in Java?
- How to remove the last node from a Singly Linked List in Java
- How to remove the first node from a Singly Linked List in Java ?
- How to check whether a linked list has a loop/cycle in java?
That’s all about How to convert sorted Linked List to balanced Binary Search Tree?
If you have any feedback or suggestion please feel free to drop in below comment box.