# Day 22 Binary Search Trees HackerRank Solution In C++

Problem:- day-22-binary-search-tree or Day 22 Binary search Tree hackerrank or Hacker Rank - Day 22 Binary search Tree or Hackerrank Day 22 Binary search Tree or BST(Binary search Tree) hackerrank or Day 22 BST(binary search tree) hackerrank solution or hackerrank Day 22 BST(binary search tree) solution or hackerrank Day 22 Binary search Tree solution or hackerrank solution BST (Binary Search Tree) solution or hackerrank solution binary search tree solution or hackerrank binary search tree solution

Binary Search Tree(BST):- I have explained everything about BST in next tutorial you can find a link to next tutorial at the end of this tutorial.

1. Binary search Tree time complexity

Algorithm Average     Worst case
Space O(n)     O(n)
Search O(log n)     O(n)
Insert O(log n)     O(n)
Delete O(log n)     O(n)

Task:- The height of a binary search tree is the number of edges between the tree's root and its furthest leaf. You are given a pointer, root, pointing to the root of a binary search tree. Complete the getHeight function provided in your editor so that it returns the height of the binary search tree.

Input Format

• The locked stub code in your editor reads the following inputs and assembles them into a binary search tree:
• The first line contains an integer, n, denoting the number of nodes in the tree.
• Each of the n subsequent lines contains an integer, data, denoting the value of an element that must be added to the BST.

Output Format

The locked stub code in your editor will print the integer returned by your getHeight function denoting the height of the BST.

Sample Input

7
3
5
2
1
4
6
7

Sample Output

3

Copy the colored code and paste it into Hacker rank editor and click to submit button, but before this process, you have to click the below link.

Solution:-

#include <iostream>
#include <cstddef>

using namespace std;

class Node{
public:
int data;
Node *left;
Node *right;
Node(int d){
data = d;
left = NULL;
right = NULL;
}
};
class Solution{
public:
Node* insert(Node* root, int data) {
if(root == NULL) {
return new Node(data);
}
else {
Node* cur;
if(data <= root->data){
cur = insert(root->left, data);
root->left = cur;
}
else{
cur = insert(root->right, data);
root->right = cur;
}

return root;
}
}

int getHeight(Node* root){
if(!root) {
return -1;
}
int leftDepth = getHeight(root->left);
int rightDepth = getHeight(root->right);

return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

}; //End of Solution
int main() {
Solution myTree;
Node* root = NULL;
int t;
int data;

cin >> t;

while(t-- > 0){
cin >> data;
root = myTree.insert(root, data);
}
int height = myTree.getHeight(root);
cout << height;

return 0;
}

Output:-

You May Also See

#### 1 comment:

1. Very useful information on Data Structures, definitely it helps us to protect our site from copied content, if you are Looking for software courses?

German Classes in Chennai
Big Data Training in Chennai
Android Training in Chennai
Selenium Training in Chennai
Digital Marketing Training in Chennai