Data Structures: Binary Search Tree (Insert, Delete, LCA & Balancing)

Implement a robust Binary Search Tree (BST) data structure in C++:

• ◦
  int value, BSTNode* left, BSTNode* right.

• ◦
  void insert(int val): Inserts a value maintaining BST property.
• ◦
  bool search(int val) const: Searches for a key in $O(\log N)$ average time.
• ◦
  void deleteNode(int val): Removes a node handling all 3 structural cases:
• ◦
  Leaf node (0 children).
• ◦
  Node with 1 child.
• ◦
  Node with 2 children (replaces with in-order successor minimum from right subtree).
• ◦
  void inorderTraversal() const: Prints sorted values.
• ◦
  void levelOrderTraversal() const: Breadth-first traversal using std::queue.
• ◦
  int findLCA(int n1, int n2) const: Finds the Lowest Common Ancestor of two nodes.
• ◦
  bool isBalanced() const: Checks if height difference between left and right subtrees of every node is at most 1.

• ◦
  Insert values: 50, 30, 70, 20, 40, 60, 80.
• ◦
  Print In-order and Level-order traversals.
• ◦
  Find LCA of (20, 40) (should be 30) and (20, 80) (should be 50).
• ◦
  Delete node 30 (2 children) and verify tree integrity.