Short Problem Definition:
Compute the height of a binary link-tree.
Link
Complexity:
expected worst-case time complexity is O(N)
expected worst-case space complexity is O(N)
Execution:
The height of a tree is the maximal height +1 of its subtrees. In this specification a tree with just the root node has a height of 0.
Solution:
'''
class Tree(object):
x = 0
l = None
r = None
'''
def getHeight(sub_T):
if sub_T == None:
return 0
return max(getHeight(sub_T.l), getHeight(sub_T.r))+1
def solution(T):
return max(getHeight(T.l), getHeight(T.r))