Issues with Binary Search Tree Insertions - Allowing Duplicates in C#
I'm having trouble with I'm implementing a Binary Search Tree (BST) in C# where I want to allow duplicate values... However, I’m running into issues when trying to insert multiple nodes with the same value. My current implementation only allows one instance of each value, and it’s causing some confusion. I’ve decided that when inserting a duplicate, it should go to the right subtree instead of being rejected or overwriting the existing value. Here's a simplified version of my `Insert` method: ```csharp public class TreeNode { public int Value; public TreeNode Left; public TreeNode Right; public TreeNode(int value) { Value = value; Left = null; Right = null; } } public class BinarySearchTree { private TreeNode root; public void Insert(int value) { root = InsertRec(root, value); } private TreeNode InsertRec(TreeNode node, int value) { if (node == null) { return new TreeNode(value); } if (value < node.Value) { node.Left = InsertRec(node.Left, value); } else { node.Right = InsertRec(node.Right, value); // This line handles duplicates } return node; } } ``` When I try to insert duplicates, everything seems fine in terms of the code execution, but when I attempt to print the elements in order, I notice that some duplicates aren't being reflected properly. I suspect that my in-order traversal might not be capturing the duplicates correctly. I've tried implementing the in-order traversal like this: ```csharp public void InOrderTraversal(TreeNode node) { if (node != null) { InOrderTraversal(node.Left); Console.WriteLine(node.Value); InOrderTraversal(node.Right); } } ``` But when I call `InOrderTraversal(root)`, the output does not show the duplicates as I expected. Could it be that the way I'm handling duplicates in the `InsertRec` method is incorrect? Or am I missing something in my traversal logic? Any insights would be greatly appreciated! What are your experiences with this? Is this even possible?