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

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.

  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.

CodePudding user response：

  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.

CodePudding user response：

You could test the tree directly and then check if the value is not an array, then return false otherwise check the left or right part.

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

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

console.log(valueInTree(tree, 72)); // false
console.log(valueInTree(tree, 1));  //  true
console.log(valueInTree(tree, 0));  //  true