Binary Search Tree

	// Node class represents each node in the BST
	class Node {
	  constructor(data) {
	    this.data = data; // Value of the node
	    this.left = null; // Pointer to left child
	    this.right = null; // Pointer to right child
	  }
	}
	
	// BinarySearchTree class provides the functionality of a BST
	class BinarySearchTree {
	  constructor() {
	    this.root = null; // Root of the BST
	  }
	
	  // Method to insert a new node with a given data
	  insert(data) {
	    const newNode = new Node(data);
	    if (this.root === null) {
	      this.root = newNode; // If tree is empty, new node becomes root
	    } else {
	      this.insertNode(this.root, newNode); // Else, use helper method to find the right position
	    }
	  }
	
	  // Helper method to insert a node in the tree by recursively finding its correct position
	  insertNode(node, newNode) {
	    if (newNode.data < node.data) {
	      // If new node's data is less than current node's data
	      if (node.left === null) {
	        node.left = newNode; // Insert new node as left child
	      } else {
	        this.insertNode(node.left, newNode); // Continue searching in left subtree
	      }
	    } else {
	      if (node.right === null) {
	        node.right = newNode; // Insert new node as right child
	      } else {
	        this.insertNode(node.right, newNode); // Continue searching in right subtree
	      }
	    }
	  }
	
	  // Method to search for a node with a given data
	  search(node, data) {
	    if (node === null) {
	      return null; // Return null if node is not found
	    } else if (data < node.data) {
	      return this.search(node.left, data); // Search in left subtree
	    } else if (data > node.data) {
	      return this.search(node.right, data); // Search in right subtree
	    } else {
	      return node; // Node found, return it
	    }
	  }
	
	  // Helper method to find the node with minimum value (used in deletion)
	  findMinNode(node) {
	    if (node.left === null) {
	      return node; // Leftmost node will be the min node
	    } else {
	      return this.findMinNode(node.left); // Continue searching in left subtree
	    }
	  }
	
	  // Method to delete a node with a given data
	  delete(data) {
	    this.root = this.deleteNode(this.root, data); // Start deletion from the root
	  }
	
	  // Helper method to delete a node by recursively finding and removing it
	  deleteNode(node, key) {
	    if (node === null) {
	      return null; // Node not found, return null
	    } else if (key < node.data) {
	      node.left = this.deleteNode(node.left, key); // Continue searching in left subtree
	      return node;
	    } else if (key > node.data) {
	      node.right = this.deleteNode(node.right, key); // Continue searching in right subtree
	      return node;
	    } else {
	      // Node with only one child or no child
	      if (node.left === null) {
	        return node.right;
	      } else if (node.right === null) {
	        return node.left;
	      }
	
	      // Node with two children: Get the inorder successor (smallest in the right subtree)
	      let aux = this.findMinNode(node.right);
	
	      // Copy the inorder successor's content to this node
	      node.data = aux.data;
	
	      // Delete the inorder successor
	      node.right = this.deleteNode(node.right, aux.data);
	      return node;
	    }
	  }
	
	  // Helper methods for tree traversal
	
	  // In-order traversal: left, root, right
	  inOrder(node) {
	    if (node !== null) {
	      this.inOrder(node.left);
	      console.log(node.data);
	      this.inOrder(node.right);
	    }
	  }
	
	  // Pre-order traversal: root, left, right
	  preOrder(node) {
	    if (node !== null) {
	      console.log(node.data);
	      this.preOrder(node.left);
	      this.preOrder(node.right);
	    }
	  }
	
	  // Post-order traversal: left, right, root
	  postOrder(node) {
	    if (node !== null) {
	      this.postOrder(node.left);
	      this.postOrder(node.right);
	      console.log(node.data);
	    }
	  }
	}
	
	// Example Usage
	const BST = new BinarySearchTree();
	BST.insert(15);
	BST.insert(25);
	BST.insert(10);
	BST.insert(7);
	BST.insert(22);
	BST.insert(17);
	BST.insert(13);
	BST.insert(5);
	BST.insert(9);
	BST.insert(27);
	
	let root = BST.getRootNode(); // Note: getRootNode method should be defined in the class
	console.log('In-order Traversal:');
	BST.inOrder(root); // In-order Traversal
	console.log('Pre-order Traversal:');
	BST.preOrder(root); // Pre-order Traversal
	console.log('Post-order Traversal:');
	BST.postOrder(root); // Post-order Traversal
	
	console.log('Searching for 22:');
	let found = BST.search(root, 22);
	console.log(found);