Problem : Write a Hacker Rank Solution For Day 22 : Binary Search Trees or Hacker Rank Solution Program In Python and java For ” Day 22 : Binary Search Trees ” or Hacker Rank 30 days of code in Python and Java Solution: Day 22: Binary Search Trees or Hackerrank solution for 30 Days of Code Challenges or Hacker rank 30 days of code in Python and Java Solution, Day 22:Binary Search Trees , or Python and java Logic & Problem Solving: Day 22: Binary Search Trees

What is Binary Search Tree ? In computer science, a binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree, whose each internal nodes store a key greater than all the keys in the node’s left subtree and less than those in its right subtree. A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties − The value of the key of the left sub-tree is less than the value of its parent (root) node’s key. The value of the key of the right sub-tree is greater than or equal to the value of its parent (root) node’s key.

HackerRank Problem :

Objective
Today, we’re working with Binary Search Trees (BSTs). Check out the Tutorial tab for learning materials and an instructional video!

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, , 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, , denoting the number of nodes in the tree.
Each of the  subsequent lines contains an integer, , 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

Explanation

The input forms the following BST:

The longest root-to-leaf path is shown below:

There are  nodes in this path that are connected by  edges, meaning our BST’s . Thus, we print  as our answer.

Solution :

public static int getHeight(Node root){
    //Write your code here
      if(root ==null)
          return -1;
      int left=getHeight(root.left);
      int right=getHeight(root.right);
      return Math.max(left, right) + 1;
  }
HackerRank Day 22 : Java / python Solution 30 days of code : Binary Search Trees

Solution in Python :

HackerRank Day 22 : Python Solution 30 days of code : Binary Search Trees

class Node:
    def __init__(self, data):
        self.right = self.left = None
        self.data = data


class Solution:
    def insert(self, root, data):
        if root is None:
            return Node(data)
        else:
            if data <= root.data:
                cur = self.insert(root.left, data)
                root.left = cur
            else:
                cur = self.insert(root.right, data)
                root.right = cur
        return root

    def getHeight(self, root):
        return -1 if root is None else 1 + max(self.getHeight(root.left), self.getHeight(root.right))


T = int(input())
myTree = Solution()
root = None
for i in range(T):
    data = int(input())
    root = myTree.insert(root, data)
height = myTree.getHeight(root)
print(height)

Leave a Reply

Your email address will not be published.