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 array to balanced binary search tree.
When you run above program, you will get below output:
Algorithm:
You might know that inorder traversal of binary search tree results in sorted array. We will use this property to convert sorted array to balanced binary search tree, so middle element of array or sub array will always be root for that array or subarray.
- Initialise two variables start and end with 0 and arr.length -1.
- Find middle element of array using start and end.
- Make middle element root element of tree.
- Recursively traverse left subtree, find middle and make it root node of left subtree
- Recursively traverse right subtree, find middle and make it root node of right subtree.
Java code to convert sorted array to balanced binary search tree:
|
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 |
package org.arpit.java2blog.binarysearchtree; public class BinarySearchTreeSortedArrayMain { 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 static void main(String[] args) { // Creating a binary search tree int arr[]={10,20,30,40,50,60,70,80,90}; TreeNode rootNode = createBinarySearchTreeFromSortedArray(arr,0,arr.length-1); System.out.println("Preorder traversal of created binary search tree :"); preOrder(rootNode); } public static TreeNode createBinarySearchTreeFromSortedArray(int[] arr,int start,int end) { if (start > end) { return null; } /* Get the middle element and make it root */ int mid = (start + end) / 2; TreeNode node = new TreeNode(arr[mid]); /* Recursively construct the left subtree and make it left child of root */ node.left = createBinarySearchTreeFromSortedArray(arr, start, mid - 1); /* Recursively construct right subtree and make right child of the root */ node.right = createBinarySearchTreeFromSortedArray(arr, mid + 1, end); return node; } } |
|
1 2 3 4 |
Preorder traversal of created binary search tree : 50 20 10 30 40 70 60 80 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.
