Implementing a Binary Search Tree in JavaScript

Binary Search Trees (BSTs) are fundamental data structures used for efficient searching, insertion, and deletion of data. This challenge asks you to implement a BST in JavaScript, focusing on core operations like insertion, searching, and in-order traversal. Building a BST will solidify your understanding of tree structures and recursive algorithms.

Problem Description

You are tasked with creating a BinarySearchTree class in JavaScript. This class should support the following operations:

• insert(value): Inserts a new node with the given value into the BST. The value should be placed in the correct position to maintain the BST property (left subtree values are less than the node's value, and right subtree values are greater).
• search(value): Searches for a node with the given value in the BST. Returns true if the value is found, and false otherwise.
• inOrderTraversal(): Performs an in-order traversal of the BST. This traversal should return an array containing the values of the nodes in ascending order.

Key Requirements:

• The BST should maintain the BST property at all times.
• The insert method should handle duplicate values (you can choose to either ignore them or allow them – clearly document your choice).
• The search method should efficiently locate a value within the tree.
• The inOrderTraversal method should return a sorted array of the tree's values.

Expected Behavior:

The class should be initialized with an empty tree. Subsequent calls to insert should correctly add nodes. search should accurately determine if a value exists. inOrderTraversal should return a sorted array representing the tree's contents.

Edge Cases to Consider:

• Inserting into an empty tree.
• Inserting duplicate values.
• Searching for a value that doesn't exist.
• Handling skewed trees (trees where all nodes are on one side).
• Empty tree traversal.

Examples

Example 1:

Input:
let bst = new BinarySearchTree();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.insert(4);
bst.insert(6);
bst.insert(8);

Output: [2, 3, 4, 5, 6, 7, 8]
Explanation: The in-order traversal of the constructed BST yields the sorted array [2, 3, 4, 5, 6, 7, 8].

Example 2:

Input:
let bst = new BinarySearchTree();
bst.insert(10);
bst.search(5);

Output: false
Explanation: The value 5 is not present in the BST.

Example 3: (Edge Case - Empty Tree)

Input:
let bst = new BinarySearchTree();
bst.inOrderTraversal();

Output: []
Explanation: An empty tree's in-order traversal returns an empty array.

Constraints

• The values to be inserted will be integers.
• The number of nodes in the BST will not exceed 1000.
• The insert, search, and inOrderTraversal methods should have an average time complexity of O(log n), where n is the number of nodes in the tree. While a worst-case O(n) is possible with skewed trees, strive for efficient implementation.
• The inOrderTraversal method should return a new array, not modify the existing tree.

Notes

• Consider using recursion for the insert and inOrderTraversal methods.
• Think about how to represent a node in the BST (e.g., using an object with value, left, and right properties).
• Document your choice regarding how to handle duplicate values.
• Focus on creating a clean, well-documented, and efficient implementation. Test your code thoroughly with various inputs, including edge cases.