- Implement the binary search algorithm on a binary search tree
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.
- Rewrite the problem in your own words
- Validate that you understand the problem
- Write your own test cases
- Pseudocode
- Code!
And remember, don't run our tests until you've passed your own!
cd
into the ruby folderruby <filename>.rb
cd
into the javascript foldernode <filename>.js
cd
into the ruby folderbundle install
rspec
cd
into the javascript foldernpm i
npm test