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 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…