HeightOfTree.java

// Height Of Tree
// Send Feedback
// For a given Binary Tree of integers, find and return the height of the tree.
// Height is defined as the total number of nodes along the longest path from
// the root to any of the leaf node.
// Example:
// ALTIMAGE

// Height of the given tree is 3.
// Input Format:
// The first and the only line of input will contain the node data, all
// separated by a single space. Since -1 is used as an indication whether the
// left or right node data exist for root, it will not be a part of the node
// data.
// Output Format:
// The first and the only line of output prints the height of the given binary
// tree.
// Note:
// You are not required to print anything explicitly. It has already been taken
// care of.
// Constraints:
// 0 <= N <= 10^5
// Where N is the total number of nodes in the binary tree.

// Time Limit: 1 sec
// Sample Input 1:
// 10 20 30 40 50 -1 -1 -1 -1 -1 -1
// Sample Output 1:
// 3
// Sample Input 2:
// 3 -1 -1
// Sample Output 2:
// 1

// Following is the structure used to represent the Binary Tree Node

class BinaryTreeNode<T> {
    T data;
    BinaryTreeNode<T> left;
    BinaryTreeNode<T> right;

    public BinaryTreeNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class Solution {

    public static int height(BinaryTreeNode<Integer> root) {
        // Your code goes here
        if (root == null) {
            return 0;
        }
        int leftNodeHeight = height(root.left);
        int rightNodeHeight = height(root.right);
        return 1 + Math.max(leftNodeHeight, rightNodeHeight);
    }

}