Implement a Binary Search Tree in JavaScript

This challenge asks you to build a fundamental data structure: a Binary Search Tree (BST). BSTs are incredibly useful for efficiently searching, inserting, and deleting data. Mastering their implementation is a crucial step in understanding more complex data structures and algorithms.

Problem Description

You need to implement a BinarySearchTree class in JavaScript. This class should represent a binary search tree and support basic operations.

Key Requirements:

1. Node Structure: Each node in the BST should store a value. It should also have references to its left and right children.
2. Insertion (insert(value)): Implement a method to insert a new node with a given value into the BST. The BST property must be maintained: all values in the left subtree of a node must be less than the node's value, and all values in the right subtree must be greater than the node's value. Duplicates can be handled in a consistent way (e.g., placed in the right subtree or ignored). For this challenge, assume duplicates will be placed in the right subtree.
3. Search (search(value)): Implement a method to check if a given value exists in the BST. This method should return true if the value is found, and false otherwise.
4. Minimum Value (findMin()): Implement a method to find the smallest value in the BST.
5. Maximum Value (findMax()): Implement a method to find the largest value in the BST.

Expected Behavior:

• When inserting values, the tree should maintain its BST properties.
• The search method should be efficient, leveraging the BST structure.
• findMin and findMax should return the appropriate values.

Edge Cases to Consider:

• Inserting into an empty tree.
• Searching for a value in an empty tree.
• Searching for the root value.
• Searching for values that do not exist.
• findMin and findMax on an empty tree (should return null or undefined).

Examples

Example 1:

Input:
let bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(2);
bst.insert(5); // Duplicate
bst.insert(13);
bst.insert(22);

Output:
bst.search(10) // returns true
bst.search(7)  // returns false
bst.findMin()  // returns 2
bst.findMax()  // returns 22

Explanation: The BST is constructed as follows:

      10
     /  \
    5    15
   / \   /  \
  2   5 13   22

The search operations correctly identify existing and non-existing values. findMin returns the leftmost node's value (2), and findMax returns the rightmost node's value (22).

Example 2:

Input:
let bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);

Output:
bst.findMin() // returns 20
bst.findMax() // returns 80
bst.search(30) // returns true
bst.search(55) // returns false

Explanation: A balanced BST is formed. findMin correctly identifies the smallest element at the far left, and findMax at the far right.

Example 3: (Edge Case - Empty Tree)

Input:
let bst = new BinarySearchTree();

Output:
bst.search(5)  // returns false
bst.findMin()  // returns null (or undefined, depending on implementation choice)
bst.findMax()  // returns null (or undefined)

Explanation: For an empty tree, searches should always fail, and findMin/findMax should indicate the absence of values.

Constraints

• Node values will be integers.
• The insert method will be called at least once.
• The search method will be called at least once.
• findMin and findMax might be called on an empty tree.
• The tree can potentially become unbalanced (no AVL or Red-Black tree balancing required for this challenge).

Notes

• You will need to define a Node class (or a factory function) to represent the nodes within your BinarySearchTree.
• The insert operation can be implemented recursively or iteratively.
• The search, findMin, and findMax operations are typically implemented recursively for elegance, but iterative solutions are also valid.
• Consider how to handle the root of the tree when it's initially empty.
• For findMin, you'll traverse left as far as possible. For findMax, you'll traverse right as far as possible.