Create a Binary Search Tree (BST) with Minimal Height from a Sorted Increasing Order Array

Problem Statement

Create a binary search tree with minimal height from a sorted increasing order array. 

 

Approach

If you traverse a Binary Search Tree in inorder traversal, you will get the numbers printed in a sorted increasing order. So you can reverse process and create a binary search tree from a sorted increasing order array of integers.

We will take the middle element and make it the root node. All elements before it should be part of left subtree and all elements after it should be part of the right subtree. 

The same process will continue for all subtrees.

 

Solution

TreeNode createBST(int[] arr, int low, int high)

{

  if( low > high) return null;

 

  int mid = (high - low) + 1;

 

  TreeNode root = new TreeNode();

  root.data = arr[mid];

  root.left = createBST(arr, low, mid-1);

  root.right = createBST(arr, mid+1, high);

 

  return root;

}

 

Complexity

Time complexity is O(N)

Space complexity is O(log N)

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) ArrayLists (1) Arrays (2) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (53) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (4) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (7) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (11) Java Programmer 2 (8) Javascript Frameworks (1) Java SE Professional (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) resources (1) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)