Day22_BinarySearchTreesLongestBranch.cpp

  
// THE PROBLEM
// ***************************
// Create the function getHeight and return the value of the longest branch, given the root as input.
// Solution Created By: Dustin Kaban
// Date: June 17th, 2020
// ***************************

#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 L = getHeight(root->left);
            int R = getHeight(root->right);

            return (L > R ? L : R) + 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;
}