BST Insert

Binary Search Tree

A Binary Search Tree (BST) is a binary tree with one rule:

• Every node's value is greater than all values in its left subtree.
• Every node's value is less than all values in its right subtree.

        5
       / \
      3   7
     / \ / \
    1  4 6  8

This property makes search, insert, and delete operations efficient — each step cuts the remaining search space in half.

Inserting a Value

To insert a value, walk down the tree following BST rules until you find an empty spot:

struct Node *bst_insert(struct Node *root, int val) {
    if (root == NULL) return new_node(val);
    if (val < root->val)
        root->left = bst_insert(root->left, val);
    else if (val > root->val)
        root->right = bst_insert(root->right, val);
    return root;
}

Duplicates are ignored (neither left nor right branch taken).

Verifying with Inorder

After inserting into a BST, an inorder traversal always yields sorted output:

Insert 5, 3, 7, 1, 4 → inorder gives 1, 3, 4, 5, 7.

Your Task

Implement struct Node *bst_insert(struct Node *root, int val) that inserts val into the BST rooted at root and returns the (possibly new) root.