RECURSE

BinarySearchTreeHeight.java

import java.util.*;
import java.io.*;

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

class Solution {
	
	public static int getHeight(Node root) {
		int maxHeight = -1;
		maxHeight = getHeightR(root, maxHeight);
		return maxHeight;
	}
	
	static int getHeightR(Node node, int currentHeight) {
		if (null == node) {
			return currentHeight;
		} else {
			currentHeight++;
			int rightHeight = getHeightR(node.left, currentHeight);
			int leftHeight = getHeightR(node.right, currentHeight);
			return (rightHeight > leftHeight) ? rightHeight : leftHeight;
		}
	}
	
	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 sc = new Scanner(System.in);
		int T = sc.nextInt();
		Node root = null;
		while (T-- > 0) {
			int data = sc.nextInt();
			root = insert(root, data);
		}
		int height = getHeight(root);
		System.out.println(height);
	}
}