Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
3.
Frequently Asked Questions
3.1.
What is a Binary Search Tree?
3.2.
What is the time complexity for the approach used?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Maximum Height of the Binary Search Tree Created from the given Array

Nishant Rana
1 upvote

## Introduction

We are given an array of ‘N’ integers. We need to construct two Binary Search Trees starting from both the left and right ends, and then return the maximum height of the Binary Search Tree among both of them.

Also see, Data Structures

Let us see a few examples:-

Input: [3, 1, 5, 2, 4]

Output: 2

Explanation: The following two trees will be formed from both the left and right ends.

Both the Binary Search Trees have a height of 2. Hence, the maximum height is 2.

## Approach

We will first implement a class for Tree. We will implement the Insert function so that we can add a node to the Binary Search Tree.

Using our tree class, we will construct both the Binary Search Trees from the left and right end and then find the height of both the trees and then return the maximum among them.

Refer to the below implementation of the above approach.

``````static class node
{
int key;
node left, right;
};

// Function to create a node of a tree.
static node newNode(int item)
{
node temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}

/*
Function to insert a node to a tree
*/
static node insert(node node, int key)
{
/*

If the tree is empty,
return a new node

*/
if (node == null)
return newNode(key);

/* Otherwise, recur down the tree */
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);

/* return the (unchanged) node pointer */
return node;
}

/*
Function to Find
the maximum depth
of a tree.
*/
static int maxDepth(node node)
{
if (node == null)
return 0;
else
{

/* compute the depth of each subtree */
int lDepth = maxDepth(node.left);
int rDepth = maxDepth(node.right);

/* use the larger one */
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}

static int maxHeight(int a[], int n)
{

/*
Creating the tree
from the left end
of the array.
*/
node rootA = null;
rootA = insert(rootA, a[0]);
for (int i = 1; i < n; i++)
rootA = insert(rootA, a[i]);

/*
Creating the another
tree from the right
end of the array.
*/
node rootB = null;
rootB = insert(rootB, a[n - 1]);
for (int i = n - 2; i >= 0; i--)
rootB =insert(rootB, a[i]);

// Finding the heights of both the trees
int HeightOfA = maxDepth(rootA) - 1;
int HeightOfB = maxDepth(rootB) - 1;

return Math.max(HeightOfA, HeightOfB);
}``````

Time Complexity: The time complexity for the above approach is O(N), (where ‘N’ is the total number of nodes in the tree) because we are just constructing a tree that takes O(N) time and finding the depth of the tree also takes O(N) time.

Space Complexity: The space complexity for the above code is O(N) because we are constructing two trees of ‘N’ nodes.

Check out this problem - Root To Leaf Path

## Frequently Asked Questions

### What is a Binary Search Tree?

A tree which has utmost two children. All the nodes on the left of the current node must have a value less than the current node’s value whereas all the nodes on the right side of the current node must have a value greater than the current node’s value.

### What is the time complexity for the approach used?

The time complexity for the above approach is O(N) because we are just constructing a tree that takes O(N) time and finding the depth of the tree also takes O(N) time.

## Conclusion

In this blog, we have covered the following things:

1. We first discussed the approach to solve this problem.
2. Then we saw how we implemented the approach discussed.

If you want to learn more about Binary Search Trees and want to practice some questions which require you to take your basic knowledge on Binary Search Tree a notch higher, then you can visit our Guided Path for Binary Search Tree

Recommended Reading:

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass