Practice: Find Node in a Binary Tree
In this assignment, your task is to solve the problem "Find a Node in a Binary Search Tree." Try to solve it independently, but check the solution if you need help.
Problem Description
// Implement a function `findNodeInBST` that, given
// the root node of a binary search tree and a value,
// returns true if the value exists in the tree or
// false if it does not.
class Node {
constructor(value) {
this.val = value;
this.left = null;
this.right = null;
}
}
// Helper function for test cases
function buildTree(arr) {
if (arr.length === 0) {
return null;
}
const nodes = [];
const val = arr.shift();
const root = new Node(val);
nodes.push(root);
while (arr.length > 0) {
const curr = nodes.shift();
const leftVal = arr.shift();
if (leftVal !== null) {
curr.left = new Node(leftVal);
nodes.push(curr.left);
}
if (arr.length > 0) {
const rightVal = arr.shift();
if (rightVal !== null) {
curr.right = new Node(rightVal);
nodes.push(curr.right);
}
}
}
return root;
}
// Test cases
const tree1 = buildTree([4, 2, 7, 1, 3]);
console.log(findNodeInBST(tree1, 2) === true);
console.log(findNodeInBST(tree1, 5) === false);
const tree2 = buildTree([5, 3, 8, 1, 4, 7, 9]);
console.log(findNodeInBST(tree2, 7) === true);
console.log(findNodeInBST(tree2, 10) === false);
const tree3 = buildTree([10]);
console.log(findNodeInBST(tree3, 10) === true);
console.log(findNodeInBST(tree3, 5) === false);
const tree4 = buildTree([]);
console.log(findNodeInBST(tree4, 1) === false);
// All test cases should log true
Exercises
Write an algorithm for finding a node in a binary search tree.
In this problem, like in other binary tree problems, where depth-first search is possible, the easiest solution will be the recursive one, and for the recursive solution, we know what we need, a base case and a recursive definition.
View Our Solution Work in Code Editor
Base Case
What is our base case in this problem? Of course, if we find the node with a target value, we can return true. Is that sufficient? What happens when we reach null. This is also a base case, but what should we return? It doesn't make much sense to return true, as null is certainly not the node with the target value. If we reach null, that means the space that could potentially house our value has run out, and we can return false.
Base Case: If the node is null return false. Otherwise, if the node's value is the target value, return true.
Recursive Definition
The recursive definition is more straightforward in this case. If the node's value is greater than the target, we have to find the node on the left side. Otherwise, if it's less, we must find the node on the right side. Whenever we say "find the node," we mean invoking the recursive function with that particular side (either the left or right child).
Recursive Definition: If the node's value is greater than the target, find the node in the BST on the left side. Otherwise, find the node in the BST on the right side.
Implement a solution for finding a node in a binary search tree.
View Our Solution Work in Code Editor
function findNodeInBST(root, target) {
if (root === null) {
return false;
}
if (root.val === target) {
return true;
}
return findNodeInBST(target > root.val ? root.right : root.left, target);
}
The solution without using a ternary operator:
function findNodeInBST(root, target) {
if (root === null) {
return false;
}
if (root.val === target) {
return true;
}
if (root.val < target) {
return findNodeInBST(root.right, target);
} else {
return findNodeInBST(root.left, target);
}
}
Identify the time and space complexity of your implementation.
View Our Solution Work in Code Editor
Time Complexity: O(h), where h is the tree's height. This is because, in the worst case, we may have to traverse from the root to a leaf, and the tree might not be balanced.
Space Complexity: O(h) for the recursive implementation due to the call stack, where h is the tree's height.