CODEWITHSUNDEEP
pythontreebinary-treeavl-tree
DefinitelyAnOverflow
DefinitelyAnOverflow

Reputation: 15

How to calculate balance of AVL-Tree node recursively and in a single function? (Python)

First question here so if I omit something important please do tell me. I have a balanced AVL tree and I need to create a function that can calculate the balance of a single given node. This needs to happen in a single function and recursively. (This is in Python, by the way)

I have also included the instantiation method for the Node class, so that you can see the attributes of the nodes. So far, I have come up with this, and, while it works, it still does not fulfill the criteria:

class Node: 
    def __init__(self, value, root): 
        self.value = value # Node value
        self.left = None # Left child
        self.right = None # Right child
        self.root = root # Stores the original root of the tree

    def getBalance(self, node):
        return self.getTreeHeight(node.right)-self.getTreeHeight(node.left)
        
    def getTreeHeight(self, rootnode):
        if rootnode == None:
            return -1
        else: 
            return max(self.getTreeHeight(rootnode.left), self.getTreeHeight(rootnode.right)) + 1

Any tips would be appreciated. All I need is a nudge in the right direction, because honestly, I'm a bit stumped.

Thank you in advance!

Upvotes: 0

Views: 906

Answers (1)

trincot
trincot

Reputation: 351384

First of all some general comments on your implementation:

  • It is unusual to provide each node with a pointer to the root of the tree. This is very unpractical if you decide to add a new node at the top of the tree, making the current root a child of the new node. Then you would have to visit every node to update the reference to the root.

  • The two methods take a node as argument, but that is a pity, as self is already a node, and so that node could be the subject of the operation. This would need a minor change in getTreeHeight, as there you currently allow the argument to be None. But in the end it is better to have these methods work without argument (except self).

Now to the question. It is not possible to write a getBalance method that only calls itself and does not pass or return any extra information. This is because the notion of balance is not inductive: if you know the balance of the children of a given node, then this information is of no use to determine the balance of the node itself. So you need somehow to pass on some extra information.

One way to do this, is to add an optional parameter to getBalance which will indicate whether the function was called recursively or not. If recursively, it could return the height, if not, the balance. That way you actually merge the two functions you already wrote:

def getBalance(self, recurring=False):
    left = self.left.getBalance(True) if self.left else 0
    right = self.right.getBalance(True) if self.right else 0
    return max(left, right) + 1 if recurring else right - left

Call as:

node = root.left.right.right  # get a reference to some node in your tree
balance = node.getBalance()  # get the balance of that node (no argument!)

Upvotes: 1

Related Questions