I want to add values while a recursive loop unfolds
<p>This is a bottom up approach to check if the tree is an AVL tree or not. So how this code works is:</p>

<p>Suppose this is a tree :</p>

<pre><code>        8
    3      10
  2
1
</code></pre>

<p>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. </p>

<p>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.</p>

<pre><code>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")
</code></pre>

<p>Your immediate problem is that you don't seem to understand local and global variables.  <strong>cl</strong> and <strong>cr</strong> 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 <em>not</em> affect the values of the variables in other instances of the function.</p>

<p>A deeper problem is that you haven't thought this through for larger trees.  Assume that you <em>do</em> 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 <strong>cl</strong> and <strong>cr</strong>.  By the time you get to node 10, <strong>cl</strong> is disturbingly more than the tree depth -- I think this is a fatal error in your logic.</p>

<hr>

<p>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 <em>one simple step</em> and recur; when the recursion returns, the function does something simple with the result and returns the new result to its parent.</p>

<p>Your task is relatively simple:</p>

<pre><code>Find the depths of the two subtrees.
If their difference &gt; 1, return False
else return True
</code></pre>

<p>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 <em>also</em> check its balance at each step.  That will be your final solution.</p>

python recursion binary-tree avl-tree