CODEWITHSUNDEEP
javascriptrecursiontreebinary-search-tree
Momu
Momu

Reputation: 33

Understanding "return" when it comes to recursion

If the question you think is important the goal is pretty much. return true if same depth different parents else false;

one case: Input: root = [1,2,3,4], x = 4, y = 3 Output: false

Example 1:

var isCousins = function(root, x, y) {
    
    const xInfo = getInfo(root, x, null, 0);
    const yInfo = getInfo(root, y, null, 0);
    
    if(xInfo.parent !== yInfo.parent && xInfo.depth === yInfo.depth) return true;
    return false;
};

const getInfo = (root, x , parent, depth) => {
    
    const obj = {
        "parent": parent,
        "depth": depth
    };
    
    if(!root) return;
    if(root.val === x) return obj;
    
    else {
        parent = root.val;
        let left =  getInfo(root.left, x, parent, depth+1);
        if(left) return left;
        let right = getInfo(root.right, x, parent, depth+1);
        if(right) return right;
    }
    
}

Example 2:

var isCousins = function(root, x, y) {
    
    const xInfo = getInfo(root, x, null, 0);
    //const yInfo = getInfo(root, y, null, 0);
    
    if(xInfo.parent !== yInfo.parent && xInfo.depth === yInfo.depth) return true;
    return false;
};

const getInfo = (root, x , parent, depth) => {
    
    const obj = {
        "parent": parent,
        "depth": depth
    };
    console.log(obj)
    
    if(!root) return;
    if(root.val === x) return obj;
    
    else {
        parent = root.val;
        if(root.left) getInfo(root.left, x, parent, depth+1);
        if(root.right) getInfo(root.right, x, parent, depth+1);
    }
    
}

In example one I get the return obj, which I want.

In example two I get undefined.

How do I understand the return part of recursion? I have my base case "if(root.val === x) return obj;" why is that not enough. In example two, the way I'm thinking it should work. Once root.val == x it just returns the obj back to xInfo and yInfo, why is the return in example 1 important.

Do I need to revisit how the call stack interacts with the search? I don't understand, what I'm missing. The more I think about it the more I get confused. The example 1 I came up with just by spamming returns everywhere

Upvotes: 0

Views: 65

Answers (1)

Carcigenicate
Carcigenicate

Reputation: 45826

return returns from the current recursive function call to the previous recursive call, not the entire series of recursive calls.

When you get to the base-case, return obj; returns obj back to the previous recursive call.

If that previous recursive call was:

 let left =  getInfo(root.left, x, parent, depth+1);
 if(left) return left;

The result from the base-case is stored into left, then returned back to the recursive call that called it. Eventually, all return to the function that called them, and that eventually leads to the value being returned to xInfo in isCousins.

On the other hand though, if the previous call was this:

if(root.left) getInfo(root.left, x, parent, depth+1);

getInfo(root.left, x, parent, depth+1) evaluates to the value of obj, and then you don't do anything with it, so it's discarded.

You need to manually pass the value found in the base-case back up the stack using returns. Simply returning to the call that lead to the base-case is not enough.

Upvotes: 3

Related Questions