27/02/2018

Day 22 Binary Search Tree Hackerrank Solution In C++ | 30 Days

Day 22 Binary Search Tree Hackerrank Solution In C++. This problem statement comes under the Hackerrank 30 days of code. Binary Search Tree(BST):- I have explained everything about BST in the next tutorial you can find a link to the next tutorial at the end of this tutorial.

Day 22 Binary Search Tree Hackerrank Solution In C++

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

  1. The locked stub code in your editor reads the following inputs and assembles them into a binary search tree:
  2. The first line contains an integer, n, denoting the number of nodes in the tree.
  3. 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 code and paste it into Hacker rank editor and click to submit button, but before this process, you have to click the below link.

Submit this Solution: Click Here

Day 22 Binary Search Tree Hackerrank Solution In C++


#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) {
    //Write your code here
    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;
}

Binary Search Tree Time and Space Complexity


Binary Search Tree ComplexityAverage CaseWorst case
SpaceO(n)O(n)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)

Day 22 Binary Search Tree Hackerrank Output


Day 22 Binary Search Tree Hackerrank Output

Similar to 30 Days of Code


Previous Post
Next Post

post written by:

Hi, I’m Ghanendra Yadav, SEO Expert, Professional Blogger, Programmer, and UI Developer. Get a Solution of More Than 500+ Programming Problems, and Practice All Programs in C, C++, and Java Languages. Get a Competitive Website Solution also Ie. Hackerrank Solutions and Geeksforgeeks Solutions. If You Are Interested to Learn a C Programming Language and You Don't Have Experience in Any Programming, You Should Start with a C Programming Language, Read: List of Format Specifiers in C.
Follow Me

0 Comments: