If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.
In this post , we will see how to convert sorted LinkedList to balanced binary search tree.
There are two ways to do it.
When you run above program, you will get below output:
Time complexity : o(N).
There are two ways to do it.
Solution 1:
It is very much similar to convert sorted array to BST. Find middle element of linked list and make it root and do it recursively.
Time complexity : o(nlogn).
Solution 2:
This solution will follow bottom up approach rather than top down.
- We need to find length of linked list
- We will first create left subtree recursively using n/2 nodes.
- We will create root node and connect left subtree to the root node.
- Similarly create right subtree recursively and connect root to right subtree.
Java Program to convert sorted LinkedList to balanced BST:
|
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 |
package org.arpit.java2blog; import org.arpit.java2blog.BinarySearchTreeMain.TreeNode; public class SortedLinkedListToBSTMain { private Node head; private static class Node { private int value; private Node next; Node(int value) { this.value = value; } } public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; } } public static void preOrder(TreeNode root) { if (root == null) return; System.out.print(root.data + " "); preOrder(root.left); preOrder(root.right); } public void addToTheLast(Node node) { if (head == null) { head = node; } else { Node temp = head; while (temp.next != null) temp = temp.next; temp.next = node; } } public void printList(Node head) { Node temp = head; while (temp != null) { System.out.format("%d ", temp.value); temp = temp.next; } System.out.println(); } // Find length of linked list using iterative method public int lengthOfLinkedList() { Node temp=head; int count = 0; while(temp!=null) { temp=temp.next; count++; } return count; } public TreeNode convertSortedLinkedListToBST(int n) { /* Base Case for recursion*/ if (n <= 0) return null; /* Recursively creating the left subtree */ TreeNode left = convertSortedLinkedListToBST(n / 2); /* Create a root node*/ TreeNode root = new TreeNode(head.value); // Set pointer to left subtree root.left = left; head = head.next; /* Create right subtree with remaining nodes*/ root.right = convertSortedLinkedListToBST(n - n / 2 - 1); return root; } public static void main(String[] args) { SortedLinkedListToBSTMain list = new SortedLinkedListToBSTMain(); // Creating a linked list Node head = new Node(10); list.addToTheLast(head); list.addToTheLast(new Node(20)); list.addToTheLast(new Node(30)); list.addToTheLast(new Node(40)); list.addToTheLast(new Node(50)); list.addToTheLast(new Node(60)); list.addToTheLast(new Node(70)); list.addToTheLast(new Node(80)); list.addToTheLast(new Node(90)); System.out.println("Printing linked list :"); list.printList(head); int n =list.lengthOfLinkedList(); TreeNode bst=list.convertSortedLinkedListToBST(n); System.out.println("---------------"); System.out.println("Pre order traversal of binary search tree :"); preOrder(bst); } } |
|
1 2 3 4 5 6 7 |
Printing linked list : 10 20 30 40 50 60 70 80 90 --------------- Pre order traversal of binary search tree : 50 30 20 10 40 80 70 60 90 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
