In a traditional binary search tree (BST), duplicate values are generally not allowed because they violate the core property that all values in the left subtree must be strictly less than the parent, and all values in the right subtree must be strictly greater. However, implementations may vary. Some modified versions of BSTs allow duplicates by applying specific rules. One approach is to consistently insert duplicates into the right subtree, treating duplicate values as “greater than or equal to” the parent. Another strategy involves maintaining a count of duplicates in each node, storing how many times a value occurs without creating new nodes for duplicates. This is useful when data naturally contains repeats, like storing frequencies. However, allowing duplicates can impact the balance and performance of the tree and may complicate deletion and traversal operations. When designing or using a BST, it's important to clarify whether duplicates are permitted and how they are managed.

In-order traversal is a depth-first traversal technique used to visit the nodes of a binary search tree (BST) in a specific order. The algorithm works recursively: it visits the left subtree first, then processes the current node, and finally visits the right subtree. When this traversal is applied to a BST, it produces the node values in ascending sorted order. This is significant because it confirms the correct structure of the BST and is often used to extract the stored data as a sorted list. For example, if a BST contains the values 20, 30, 40, 50, and 60, in-order traversal would visit them in the exact order: 20 → 30 → 40 → 50 → 60. This makes in-order traversal particularly valuable in applications where ordered data retrieval is required, such as printing data in sequence or exporting it to an array. It also helps in debugging and verifying the integrity of the BST structure.

Inserting values into a binary search tree (BST) in strictly increasing or decreasing order leads to the creation of a completely unbalanced tree. Each new value is either always greater or always less than the previous one, so each node ends up with only one child, forming a structure that resembles a linked list. For example, inserting 10, 20, 30, 40, and 50 will produce a right-skewed tree where each node only has a right child. The main consequence of this is a significant drop in performance. The height of the tree becomes equal to the number of nodes, and operations such as search, insert, and delete degrade from O(log n) to O(n) time complexity. This defeats the purpose of using a BST, which is meant to be an efficient data structure. To prevent this issue, self-balancing trees like AVL or Red-Black trees are used in real-world applications to maintain a low height.

Although binary search trees (BSTs) offer efficient operations under ideal conditions, they are not always the best choice for data storage in practice. One key limitation is that their efficiency is heavily dependent on the balance of the tree. Without balancing, the performance can degrade significantly, especially with skewed data inputs like sorted lists. Additionally, BSTs are not optimal for scenarios where frequent reordering or random access is required, such as with dynamic datasets that change rapidly. In such cases, structures like hash tables or balanced search trees (e.g., AVL or Red-Black trees) might be more appropriate. BSTs also require more memory than arrays because each node must store pointers to its children, which increases overhead. Moreover, in environments with strict time constraints or where predictability of performance is critical, the non-guaranteed O(log n) time of an unbalanced BST can be a drawback. Therefore, choosing the right data structure depends on the specific requirements of the application.

Deleting a node with two children in a binary search tree (BST) is the most complex deletion case and must be handled carefully to maintain the BST properties. The standard approach is to replace the value of the node being deleted with either its in-order predecessor (the largest value in the left subtree) or its in-order successor (the smallest value in the right subtree). After the replacement, the node that held the predecessor or successor value is then deleted, which will have at most one child, making its removal straightforward. This two-step process ensures that the BST remains properly ordered. However, it can slightly alter the shape of the tree, especially if the in-order successor or predecessor was not a direct child of the node being deleted. The deletion may also impact balance, particularly if it introduces a height difference between subtrees. Therefore, in systems where maintaining balance is critical, additional rebalancing steps may be required after deletion.