Day 5: Find a Target Value in a Binary Search Tree

Learning Goals

• Implement the binary search algorithm on a binary search tree

Introduction

Given a binary search tree (BST), find the node with the target value and return the node. If the node does not exist in the tree return a falsy value, such as null or nil.

   1
  / \
-1   2

Input: root node, target = 2
Output: Node with value 2

Input: root node, target = 5
Output: null or nil

What is the time complexity of your solution? How does the complexity differ for a balanced tree versus an unbalanced tree?

Use the language of your choosing. We've included starter files for some languages where you can pseudocode, explain your solution and code.

Before you start coding

1. Rewrite the problem in your own words
2. Validate that you understand the problem
3. Write your own test cases
4. Pseudocode
5. Code!

And remember, don't run our tests until you've passed your own!

How to run your own tests

Ruby

1. cd into the ruby folder
2. ruby <filename>.rb

JavaScript

1. cd into the javascript folder
2. node <filename>.js

How to run our tests

Ruby

1. cd into the ruby folder
2. bundle install
3. rspec

JavaScript

1. cd into the javascript folder
2. npm i
3. npm test