javascript - Binary tree search not returning matching value when some nodes are null

Question

TL;DR - How do I alter this algorithm to return the matching val given a BST with null nodes?

TreeNode:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */

Given a binary tree, find the matching val. My algorithm is below

var searchBST = function(root, val) {
    const matchingNode = visitNode(root, val);
    // if no match, return null
    return matchingNode ? matchingNode : null;
};

const visitNode = (node, val) => {
    if (node.left !== null) {
        return visitNode(node.left, val)
    }
    if (node.right !== null) {
        return visitNode(node.right, val)
    }
    if (node.val === val) {
        console.log('MATCH!')
        return node;
    }
}

This works for standard trees with no null values, such as [4,2,7,1,3] and empty trees [].

I'm having an issue with trees that have null nodes, such as [18, 2, 22, null, null, null, 63, null, 84, null, null].

The function seems to stop prematurely. If I remove the returns in the first two if blocks, I'm able to stop recursing at the matching val, but unable to get the value to be returned.

How do I alter this algorithm to return the matching val given a BST with null nodes?

question from:https://stackoverflow.com/questions/65912440/binary-tree-search-not-returning-matching-value-when-some-nodes-are-null

Answer 1

You may consider the following refactored version of visitNode() below. The base case occurs when the incoming node be null, in which case the function just returns null. Otherwise, it checks if the current node matches the sought after value. If not, then it traverses either the left or right recursively.

const visitNode = (node, val) => {
    if (node == null) return null;

    if (node.val === val) {
        console.log('MATCH!')
        return node;
    }

    if (val < node.val) {
        return visitNode(node.left, val);
    }
    else {
        return visitNode(node.right, val)
    }
}