In this HackerRank Tree: height of a binary tress Interview preparation kit problem you need to complete the getHeight or height function. It must return the height of a binary tree as an integer.
Problem solution in Python programming.
class Node:
def __init__(self, info):
self.info = info
self.left = None
self.right = None
self.level = None
def __str__(self):
return str(self.info)
class BinarySearchTree:
def __init__(self):
self.root = None
def create(self, val):
if self.root == None:
self.root = Node(val)
else:
current = self.root
while True:
if val < current.info:
if current.left:
current = current.left
else:
current.left = Node(val)
break
elif val > current.info:
if current.right:
current = current.right
else:
current.right = Node(val)
break
else:
break
# Enter your code here. Read input from STDIN. Print output to STDOUT
'''
class Node:
def __init__(self,info):
self.info = info
self.left = None
self.right = None
// this is a node of the tree , which contains info as data, left , right
'''
def height(root):
leftHeight = 0
rightHeight = 0
if(root.left):
leftHeight = height(root.left) + 1
if(root.right):
rightHeight = height(root.right) + 1
if(leftHeight > rightHeight):
return leftHeight
else:
return rightHeight
tree = BinarySearchTree()
t = int(input())
arr = list(map(int, input().split()))
for i in range(t):
tree.create(arr[i])
print(height(tree.root))
Problem solution in Java Programming.
import java.util.*; import java.io.*; class Node { Node left; Node right; int data; Node(int data) { this.data = data; left = null; right = null; } } class Solution { /* class Node int data; Node left; Node right; */ public static int height(Node root) { if(root == null) { return -1; } return Math.max(height(root.left), height(root.right)) + 1; } public static 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; } } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); Node root = null; while(t-- > 0) { int data = scan.nextInt(); root = insert(root, data); } scan.close(); int height = height(root); System.out.println(height); } }
Problem solution in C++ programming.
#include <bits/stdc++.h>
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;
}
}
/*The tree node has data, left child and right child
class Node {
int data;
Node* left;
Node* right;
};
*/
int height(Node* root) {
// Write your code here.
int leftHeight=-1,rightHeight=-1;
if(root->left){
leftHeight=height(root->left);
}
if(root->right)
rightHeight=height(root->right);
return max(leftHeight,rightHeight)+1;
}
}; //End of Solution
int main() {
Solution myTree;
Node* root = NULL;
int t;
int data;
std::cin >> t;
while(t-- > 0) {
std::cin >> data;
root = myTree.insert(root, data);
}
int height = myTree.height(root);
std::cout << height;
return 0;
}
Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct node {
int data;
struct node *left;
struct node *right;
};
struct node* insert( struct node* root, int data ) {
if(root == NULL) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
} else {
struct 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;
}
}
/* you only have to complete the function given below.
node is defined as
struct node {
int data;
struct node *left;
struct node *right;
};
*/
int getHeight(struct node* root)
{
int counter_right = 0;
int counter_left = 0;
if (root == NULL)
{
return -1;
}
counter_left = getHeight(root->left);
counter_left++;
counter_right = getHeight(root->right);
counter_right++;
if (counter_left > counter_right)
{
return counter_left;
}
return counter_right;
}
int main() {
struct node* root = NULL;
int t;
int data;
scanf("%d", &t);
while(t-- > 0) {
scanf("%d", &data);
root = insert(root, data);
}
printf("%d",getHeight(root));
return 0;
}