CODEWITHSUNDEEP
javascriptalgorithmrecursionbinary-search-tree
Vtron89
Vtron89

Reputation: 35

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

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?

Upvotes: 0

Views: 708

Answers (2)

kswang
kswang

Reputation: 160

If you are looking for binary search tree, try this

if (node == null || node.val === val) 
   return node;
 
// val is greater than node's val
if (node->val < val) 
   return visitNode(node.right, val); 

// val is smaller than node's val
return visitNode(node.left, val);

Or you have to traverse the tree by DFS or BFS

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522752

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)
    }
}

Upvotes: 2

Related Questions