Ask LSBot

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

  1. 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

    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.

  2. Implement a solution for finding a node in a binary search tree.

    View Our Solution

    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);
      }
    }
    
  3. Identify the time and space complexity of your implementation.

    View Our Solution

    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.

This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you understand this chapter content with fast, focused answers.

Ask me about concepts, examples, or anything you'd like clarified from this chapter. I can explain complex topics, provide examples, or help connect ideas.

Want to know more? Refer to the LSBot User Guide.

This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you think through this exercise by providing hints and guidance, without giving away the solution.

You can ask me about your approach, request clarification on the problem, or seek help when you feel stuck.

Want to know more? Refer to the LSBot User Guide.