Solution to Tree-Height by codility

10 Replies to “Solution to Tree-Height by codility”

1. Java version:

   1 2 3 4 5 6 7 8 9

   class Solution {     public int solution(Tree T) {         if(T == null) return -1;         int result = 0;         result = Math.max(result, 1+solution(T.l));         result = Math.max(result, 1+solution(T.r));         return result;     } }

   Reply

   • Thanks for sharing your solution!
     For posting code, please add the code inside a <pre> </pre> section, rather than <code> </code>.
     BTW, the first Math.max is not necessary.

     Reply

   • Or more simply

     1 2 3 4 5 6 7

     class Solution {     public int solution(Tree T) {         if (T==null)             return -1;         return 1+Math.max(solution(T.l), solution(T.r));     } }

     Reply

     • Elegant solution! Thank you!

       Reply

2. Hi Guys! I thought about doing this solution too but isn’t this n^2 time complexity ?
   In the end the performance of my test was not assessed, but other solutions I tried before with recursion were always a bit slow.
   Miguel

   Reply

   • >> binary tree T consisting of N nodes
     The code access each node, once and only once. Therefore the complexity is O(N).

     Reply

3. 1 2 3 4 5

   def solution(T):      if (T==None):         return -1      else:         return 1+ max(solution(T.l), solution(T.r))

   Reply

4. Quick solution in C# (left in some code that I refactored out)… 100%

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   using System; // you can also use other imports, for example: // using System.Collections.Generic;   // you can write to stdout for debugging purposes, e.g. // Console.WriteLine("this is a debug message");   class Solution {     public int solution(Tree T) {         // write your code in C# 6.0 with .NET 4.5 (Mono)         if (T == null)             return -1;              //int leftheight = solution(T.l);         //int rightheight = solution(T.r);              //return leftheight > rightheight ? leftheight + 1 : rightheight +1;         return 1 + Math.Max(solution(T.l), solution(T.r));     } }

   Reply

5. What is the problem for this? It says tree height but it doesn’t look like the tree height problem I had on the test. Which was to make the minimum number of cuts so that trees have heights going up and down alternately. If it is for that problem then I’m somewhat lost.

   Reply

   • I do not know what is your test. In the original post, there is a link to the question. Please refer to it.

     Reply