Day 22: Binary Search Trees – Hackerrank 30 Days Of Code Solution

June 14, 2024

Let’s solve Day 22: Binary Search Trees. Binary Search Trees (BSTs) are fundamental data structures in computer science, widely used for efficient storage and retrieval of data. Join us on this exciting journey to explore BSTs and their practical application.😍

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.

Sample Input

Sample Output

Explanation

To solve this challenge, we need to implement the getHeight function, which calculates and returns the height of a given binary search tree. The height of a binary tree is defined as the number of edges between the root and the furthest leaf node.

The getHeight function should recursively traverse the tree and determine the maximum height among the left and right subtrees, adding 1 to account for the root node. If the tree is empty (root is null), the height is considered to be -1.

Day 22: Binary Search Trees Solution In Javascript

JavaScript

if (root === null) return -1;

return Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;

Day 22: Binary Search Trees Solution In C++

C++

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        this->left = nullptr;
        this->right = nullptr;
    }
};

class BinarySearchTree {
public:
    Node* root;

    Node* insert(Node* root, int data) {
        if (root == nullptr) {
            this->root = new Node(data);
            return this->root;
        }

        if (data <= root->data) {
            if (root->left) {
                insert(root->left, data);
            } else {
                root->left = new Node(data);
            }
        } else {
            if (root->right) {
                insert(root->right, data);
            } else {
                root->right = new Node(data);
            }
        }

        return this->root;
    }

    int getHeight(Node* root) {
        if (root == nullptr) return -1;
        return max(getHeight(root->left), getHeight(root->right)) + 1;
    }
};

int main() {
    BinarySearchTree tree;
    Node* root = nullptr;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int data;
        cin >> data;
        root = tree.insert(root, data);
    }
    cout << tree.getHeight(root) << endl;
    return 0;
}

Day 22: Binary Search Trees Solution In Java

Java

class Node {
    int data;
    Node left;
    Node right;
    
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class BinarySearchTree {
    Node root;

    Node insert(Node root, int data) {
        if (root == null) {
            this.root = new Node(data);
            return this.root;
        }

        if (data <= root.data) {
            if (root.left != null) {
                insert(root.left, data);
            } else {
                root.left = new Node(data);
            }
        } else {
            if (root.right != null) {
                insert(root.right, data);
            } else {
                root.right = new Node(data);
            }
        }

        return this.root;
    }

    int getHeight(Node root) {
        if (root == null) return -1;
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BinarySearchTree tree = new BinarySearchTree();
        Node root = null;
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int data = scanner.nextInt();
            root = tree.insert(root, data);
        }
        System.out.println(tree.getHeight(root));
        scanner.close();
    }
}

Day 22: Binary Search Trees Solution In Python

Python

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

Day 22: Binary Search Trees Solution In PHP

PHP

<?php

public function getHeight($root){
    if($root==null) return -1;
    return max($this->getHeight($root->left), $this->getHeight($root->right)) + 1;
}

Learning from this Question

By solving the “Day 22: Binary Search Trees” challenge, you can learn several important concepts:

Binary Search Trees (BSTs): You will gain a deep understanding of BSTs, their properties, and their operations.
Tree traversal: You will practice traversing binary trees using recursive algorithms.
Recursion: You will reinforce your understanding of recursion and its application in solving tree-related problems.
Height calculation: You will learn how to calculate the height of a binary tree using a recursive approach.
Data structures: You will strengthen your knowledge of fundamental data structures, such as trees and nodes.
Problem-solving skills: You will enhance your problem-solving skills by designing and implementing a solution that meets the given requirements.

Conclusion

The “Day 22: Binary Search Trees” challenge introduces the concept of binary search trees and their height calculation. By implementing the getHeight function, you will gain valuable experience in working with BSTs, recursion, and tree traversal algorithms. The complete code for this challenge is available in my GitHub repository✨.

This exercise reinforces the importance of binary search trees in computer science and data structures, as they provide efficient operations for searching, inserting, and deleting data⭐.

“Progress is possible only if we train ourselves to think about programs without thinking of them as pieces of executable code. ”

― Edsger W. Dijkstra