Space complexity of checking if binary tree is balanced

42 Views Asked by At

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?

0

There are 0 best solutions below