I'm trying to understand the time and space complexity of this code for determining whether a Binary tree is balanced:
def height(t):
if t is None:
return 0
return max(height(t.left), height(t.right)) + 1
def is_balanced_binary_tree(tree: BinaryTreeNode) -\> bool:
if tree is None:
return True
if abs(height(tree.left) - height(tree.right)) > 1:
return False
return is_balanced_binary_tree(tree.left) and is_balanced_binary_tree(tree.right)
Time complexity is O(NlogN); but I'm not sure how to think about space complexity in the context of 4 function calls made from is_balanced_binary_tree and 2 in height. What we do know is that from the root node, we can expect to call 4 * H functions, where H is the height of the tree. Does this generalize over touching N nodes, to give a space complexity of 4*H*N?