Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

How to check right side of Binary tree. Search item in a tree

I have an array.

const arr1 = [3, [ 8, [ 5, 4, null], 11], [ 7, [ 1, 0, null], null]] 

I want to write a function, which should check if given value is in tree or not.

Here is my function.

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

  function valueInTree(tree, val) {
    if(tree[0] === val || tree[1] === val || tree [2] === val){
        return true;
    }

    if (Array.isArray(tree[1])){
        return valueInTree(tree[1],val)
    }
    if (Array.isArray(tree[2])){
        return valueInTree(tree[2],val);
    }

    return false; 
}

console.log(valueInTree(arr1, 72));

Below is a visual of the given array.

//                      3
//                    /   \
//                   8     7
//                  /\     /\
//                 5 11   1   N
//                /\     / \
//               4  72  0   N

So, my question.
As you can see, my function cannot check the right side of the tree. For example, it can find numbers 3, 8, 5, and 4. But when I try to find 7 or 11 it returns false.

>Solution :

  function valueInTree(tree, val) {
    if(tree[0] === val || tree[1] === val || tree [2] === val){
        return true;
    }

    if (Array.isArray(tree[1])){
        if (valueInTree(tree[1],val))
          return true
    }
    if (Array.isArray(tree[2])){
        return valueInTree(tree[2],val);
    }

    return false; 
}

console.log(valueInTree(arr1, 72));

The only problem with your code is that it never checks the right subtree because if the left is a subtree it returns directly whether the element is in it. Check if the element was found in the left subtree and return true if and only if it is true. This way you give the algorithm a chance to check the right subtree too. I made a small change to make that happen.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading