Codility Tree Height

Posted on November 6, 2013

Last updated on November 24, 2013

In this article I will provide a solution to the Tree Height sample Codility problem. The problem description is copyrighted, so have a look at the link for the description. The problem itself is quite easy, but I’ll still include it here for the sake of completeness of having solutions to all problems for which Codility does not post a solution. The gist of the problem is as follows:

Given a binary tree, its height is the length of the longest possible path from the root to a leaf. Calculate the height of a binary tree.

Since the Codility problem restrictions are small, the simplest recursive solution comes to mind since under these restrictions we will not run out of stack space. The idea is as follows: Recursively compute the height of the left and right subtrees; then, the answer is just the maximum of the height of the left and right subtree.

The 100/100 code in Java:

public int maxHeight(Tree T) {
    int t1l = 0;
    int t2l = 0;
    if(T.l != null){
        t1l = 1 + maxHeight(T.l);
    if(T.r != null){
        t2l = 1 + maxHeight(T.r);
    return Math.max(t1l,t2l);
Markdown SHA1: cbf8beadd3412f8f6bfa6e0c187c95c1d582a6d7