Game development as an Art

Sato Game Dev

Code Exercises


Binary Search Trees


Source: Hacker rank

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

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, n, denoting the number of nodes in the tree.
Each of the 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

Explanation

The input forms the following BST:

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

There are 4 nodes in this path that are connected by 3 edges, meaning our BST's height=3. Thus, we print 3 as our answer.
My solution:
C#:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarySearchTrees
{
    class Program
    {

        static int getHeightRecursive(Node root, int maxHeight, int actualHeight)
        {
            //Pre-order 
            //visit Node
            if (root == null)
                return maxHeight;
            else
            {
               if (actualHeight > maxHeight)
                    maxHeight = actualHeight;

                //go to left node
                int leftHeight = getHeightRecursive(root.left, maxHeight, actualHeight + 1);
                if (leftHeight > maxHeight)
                    maxHeight = leftHeight;

                //go to right node
                int rightHeight = getHeightRecursive(root.right, maxHeight, actualHeight + 1);
                if (rightHeight > maxHeight)
                    maxHeight = rightHeight;
            }
            return maxHeight;
        }

        static int getHeight(Node root)
        {
            //Write your code here
            int maxHeight = 0;
            int actualHeight = 0;
            return getHeightRecursive(root, maxHeight, actualHeight);
        }

        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;
            }
        }

        static void Main(string[] args)
        {

            Node root = null;
            int T = Int32.Parse(Console.ReadLine());
            while (T-- > 0)
            {
                int data = Int32.Parse(Console.ReadLine());
                root = insert(root, data);
            }
            int height = getHeight(root);
            Console.WriteLine(height);
            Console.ReadKey();
        }
    }
}