Aakash Shah - 2 months ago 7

Python Question

This is a bottom up approach to check if the tree is an AVL tree or not. So how this code works is:

Suppose this is a tree :

`8`

3 10

2

1

The leaf node is checked that it is a leaf node(here 1). It then unfolds one recursion when the node with data 2 is the current value. The value of cl = 1, while it compares the right tree. The right branch of 2 is empty i.e does not have any children so the avl_compare will have (1, 0) which is allowed.

After this i want to add one value to cl so that when the node with data 3 is the current value, the value of cl = 2. avl_check is an assignment question. I have done this on my own but i need some help here to play with recursive functions.

`def avl_check(self):`

cl = cr = 0

if(self.left):

self.left.avl_check()

cl+=1

if(self.right):

self.right.avl_check()

cr += 1

if(not self.avl_compare(cl,cr)):

print("here")

Answer

Your immediate problem is that you don't seem to understand local and global variables. **cl** and **cr** are local variables; with the given control flow, the only values they can ever have are 0 and 1. Remember that each instance of the routine gets a new set of local variables: you set them to 0, perhaps increment to 1, and then you return. This does *not* affect the values of the variables in other instances of the function.

A deeper problem is that you haven't thought this through for larger trees. Assume that you *do* learn to use global variables and correct these increments. Take your current tree, insert nodes 4, 9, 10, and 11 (nicely balanced). Walk through your algorithm, tracing the values of **cl** and **cr**. By the time you get to node 10, **cl** is disturbingly more than the tree depth -- I think this is a fatal error in your logic.

Think through this again: a recursive routine should not have global variables, except perhaps for the data store of a dynamic programming implementation (which does not apply here). The function should check for the base case and return something trivial (such as 0 or 1). Otherwise, the function should reduce the problem *one simple step* and recur; when the recursion returns, the function does something simple with the result and returns the new result to its parent.

Your task is relatively simple:

```
Find the depths of the two subtrees.
If their difference > 1, return False
else return True
```

You should already know how to check the depth of a tree. Implement this first. After that, make your implementation more intelligent: checking the depth of a subtree should *also* check its balance at each step. That will be your final solution.

Source (Stackoverflow)

Comments