Implement a Binary Search Tree
HANDS-ON PRACTICE
Implement a Binary Search Tree
Choose C, C++, Java, or Python and implement a binary search tree that rejects duplicate values.
- Maintain the root and element count. Implement emptiness, size, height, and clear operations.
- Implement lookup and insertion. Inserting an existing value must leave both the structure and count unchanged.
- Implement deletion for leaves, nodes with one or two children, and the root. Removing a missing value must not change the count.
- Implement preorder, inorder, postorder, and level-order traversal.
- Insert 8, 3, 10, 1, 6, 14, 4, 7, 13 and check inorder [1,3,4,6,7,8,10,13,14]. Insert 6 again, remove missing 99, then remove 1, 14, 8; check [3,4,6,7,10,13].
- Separate declarations and definitions into header and implementation files for C and C++. In C, free removed nodes and all nodes when clearing.