BST insert

Challenge

Insert a value into a binary search tree, keeping the BST ordering and ignoring duplicates.

The grader supplies this node type:

typedef struct bst { int v; struct bst *l, *r; } bst_t;

Task

Implement bst_t *bst_insert(bst_t *root, int v) that inserts v and returns the (possibly new) root. No main — the grader calls it.

Input

• root: the current root, or NULL for an empty tree.
• v: the value to insert.

Output

The root of the tree after insertion. Smaller values go left, larger go right. If v already exists, the tree is unchanged and the same root is returned.

Example

insert 5,3,8,1,4 then an in-order walk   ->   1,3,4,5,8
inserting a duplicate (e.g. another 3)   ->   no new node added

Edge cases

• Inserting into an empty tree allocates and returns the new root.
• Duplicate values are ignored (no second node).

Rules

• Allocate new nodes with malloc; reassign child links from the recursive call so new subtrees attach.

Input format

root (or NULL) and the int value v to insert.

Output format

The root after inserting v (unchanged if v already exists).

Constraints

Allocate nodes with malloc; duplicates are ignored.

Starter code

#include <stdlib.h>

bst_t *bst_insert(bst_t *root, int v) {
    /* TODO */
    return root;
}