Maximum height of the binary search tree created from the given array

Nishant Rana
Last Updated: May 13, 2022

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.

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.

 

FAQs:

  1. 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.
  2. 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.

 

Key Takeaways: 

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 Tree 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

 

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








 

Was this article helpful ?
1 upvote