calculate balance factors of nodes recursively only root is given and in a single pass

Question

---

the problem is we shouldnt use any tree traversals

def fill_balance(root):

if root == None : return None root.value = fill_balance(root.left)-fill_balance(root.right)

here is my code to calculate balance of each node of a tee whose root is given .. how can i fix my code ? the solution must be in a single pass root is generated and function must be recursive .

Answer 1

I think here is the solution:

def get_height(node):
    if node is None:
        return 0
    else:
        if node.height is None:
            node.height = max(get_height(n.left),get_height(n.right))+1
        return node.height

def fill_balance(node):
    if node == None:
        return
    else:
        node.balance_factor = get_height(node.left)-get_height(node.right)
        fill_balance(node.left)
        fill_balance(node.right)
        return

fill_balance(root)