CODEWITHSUNDEEP
recursiontreebinary-treebinary-search-tree
jlin90
jlin90

Reputation: 1

Confusion about recursion for BST

Is there an easy way to understand when you can just call the recursive method vs having to set that recursive method to a variable?

For example...
Just calling the recursive function to traverse:
self.recurse(node.left)
self.recurse(node.right)

Having to set the recursive function to node.left and node.right:
node.left = self.recurse(node.left)
node.right = self.recurse(node.left)

Another example is to delete a node in a bst you have to set the recursive function to root.left and root.right... I get it but not completely... is there a easy way to understand when you can just call the recursive function vs having to set it to node.left, node.right..etc...?

def deleteNode(self, root: TreeNode, key:int) -> TreeNode:
    
    if not root:
        return root
    if key < root.val:
        root.left = self.deleteNode(root.left,key)
    elif key > root.val:
        root.right = self.deleteNode(root.right,key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        
        root.val = self.successor(root.right)
        root.right = self.deleteNode(root.right,root.val)
    
    return root

Upvotes: 0

Views: 190

Answers (1)

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1539

To understand this two above scenarios (Simple Recursive Call and Set result of Recursive call to a Variable), just try to understand the following code/function.

Let's say, you have a TREE, which contains a value in every node where value is either negative or positive. Now let's say, you are going to count how many nodes are there whose value is Positive. The TREE structure for this problem is like following:

TREE{
  Integer val;
  TREE left = right = null;
}

Now you gave me this problem to solve. And I wrote a function/method which will count nodes with positive value. The function is following:

Integer countNodes(TREE node){
  if(node == null){
     return 0;
  }else{
      Integer count = 0; // which will count how many nodes are there with positive value
      if(node.val >= 0){
         count += 1; // if the value is positive I incremented count
      }

      // and we are checking every other nodes present in the TREE
      getCount(node.left);
      getCount(node.right);

     // and return the final result
     return count;
  }
}

Now I returned my function to you, and you executed! But what! There is a big WRONG! It's giving wrong result, over and over again!!

But why???

Let's analysis.

 if(node.val >= 0){
     count += 1;
 }

Up to that we were right! But the problem was, we were incremented the count, but wasn't use it! Each time we was calling function recursively, a new stack frame was created, a new variable named "count" was created, but we were not using this value!

To use the variable "count", we need to re-initialize the returned value of every recursive call to the variable, that's the way we can keep a link between the current stack-frame and the previous stack-frame and the previous of previous stack-frame and goes onn!.. we need to change little-bit in the function countNodes like following:

  if(node.val >= 0){
      count += 1;
  }

  count += getCount(node.left);  // re-initialize count in each recursive call
  count += getCount(node.right); // re-initialize count in each recursive call

  return count;

Now everything we'll be alright! this code will work perfectly!

The above scenarios is implies your problem.

self.recurse(node.left)

self.recurse(node.right)

this is nothing but simple traversing over all the nodes.

But if you need to use the returned result of every recursion, you need to initialize/re-initialize the returned value to a variable. That's what is happening with:

node.left = self.recurse(node.left)

node.right = self.recurse(node.left)

I HOPE this long (bit long) explanation will help to go further. Happy Coding! : )

Upvotes: 0

Related Questions