Binary Search Tree Recursion returning undefined - Javascript

Question

I have a binary search tree stated below:

I am looking to find an element, for example "3", and be able to get back an array of its path, which would be [3, 2, 4].

My issue is that when I return from the recursive function, I get back undefined. Additionally, when I console.log the path before it is returned, the console.log is correct but I do not get anything from the return.

Below is the code that I am trying to fix

let searchItem = (root, value, path) => {
    const curr = root;
    if(curr.val === value){
        console.log(path)
        return path;
    }
    if(curr.right){
        searchItem(curr.right, value, [curr.right.val, ...path])
    }
    if(curr.left){
        searchItem(curr.left, value, [curr.left.val, ...path])
    } 
}

let path1 = searchItem(root, 2, [root.val]);


console.log(path1)

Nina's answer below might give you some more insight on that @Brian. — Ivar
– Ivar, Commented Sep 2, 2020 at 14:54

Nina Scholz · Accepted Answer · 2020-09-02 17:48:37Z

1

You need to check the value and return the result of walking the branch.

let searchItem = (node, value, [...path] = []) => {
        if (!node) return;
        path.unshift(node.val);
        if (node.val === value) return path;
        return searchItem(node.left, value, path)
            || searchItem(node.right, value, path);
    },
    tree = { val: 4, left: { val: 2, left: { val: 1 }, right: { val: 3 } }, right: { val: 6 } };

console.log(searchItem(tree, 2));
console.log(searchItem(tree, 3));
console.log(searchItem(tree, 6));

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Sep 2, 2020 at 17:48

answered Sep 2, 2020 at 14:51

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Brian R Over a year ago

Hey Nina, this works but I am actually thinking of a situation where I am trying to find an ID, for example, saying I was trying to find a specific member of an organization in an org chart. I would be looking for a userID which would not necessarily have an ID value smaller than its parent. Is that possible to do in this situation? Otherwise, I think your solution works.

Nina Scholz Over a year ago

then you need to visit all branches.

Brian R Over a year ago

Thanks again for taking a look Nina, I really appreciate it. I took a look at this and it still seems to have a similar issue to what I was having before. For example, if we searched for 6 which is on the right side, the searchItem for node.right will never fire and it will never find 6. I'm getting a heap out of memory error when I search for 6.

Brian R Over a year ago

It works for the tree you provided but not for the tree I am using. I'm starting to wonder if there is something weird happening with the one I am using. But yes, it works perfectly. Thanks again for taking the time to help me. I would upvote your answer but Im not able to yet because I am a new user :). Cheers!

Collectives™ on Stack Overflow

Binary Search Tree Recursion returning undefined - Javascript

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related