Question Name: TreeHeight
Classic recursion problem.
Solution to Tree-Height by codility
if T.l == None and T.r == None:
# Has no subtree
elif T.l == None:
# Only has right subtree
return 1 + solution(T.r)
elif T.r == None:
# Only has left subtree
return 1 + solution(T.l)
# Have two subtrees
return 1 + max(solution(T.l), solution(T.r))
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.
Or more simply
Elegant solution! Thank you!
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.
>> binary tree T consisting of N nodes
The code access each node, once and only once. Therefore the complexity is O(N).
Quick solution in C# (left in some code that I refactored out)… 100%
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.
I do not know what is your test. In the original post, there is a link to the question. Please refer to it.