# BST Operations: Playground (Part 1)

Implement generic BST algorithms in C.

## Implementing the operations

Welcome to the first playground lesson where you’ll implement the pseudocode from the previous lesson.

We’ll first briefly go over the functions that you need to implement. Then, you can start implementing them in the code widget below.

### Helper functions

Before implementing any algorithms, you should implement two helper functions.

`allocNode`

will allocate a new node inside the generic tree.- We suggest accepting a
`value`

`void*`

that you’ll use to initialize the`value`

field inside the node. The expectation is that the caller of`allocNode`

will provide freshly dynamically allocated memory, and`allocNode`

can take ownership of it. We guarantee this is the case inside the project during the automatic testing. - The
`left`

and`right`

fields should point to empty trees. In other words,`allocNode`

should allocate a tree consisting of only one node.

- We suggest accepting a
`freeBst`

to fully deallocate a binary search tree and its values. You may need to use a generic helper function to free the value. Since the implementation is generic, different data types may need to be freed differently.

### The `findNode`

function

Implement the `findNode`

function. It should accept a binary search tree and a value.

- If the tree contains a node with the given value, return that node.
- If the tree doesn’t contain the given value, return the insertion point of that value inside the tree.
- Return
`NULL`

if the tree is empty.

### The `contains`

function

Implement the `contains`

function. It should accept a binary search tree and a value. Return `1`

if the tree contains a node with the given value. Otherwise, return `0`

.

You may want to use the `findNode`

function for implementing `contains`

.

### The `insertNode`

function

Implement the `insertNot`

function. It should accept a binary search tree and a value. The function should insert the `value`

inside the tree at the appropriate location, according to the BST ordering property. Don’t perform the insertion if the tree already contains the value. Return `1`

upon a successful insertion and `0`

otherwise.

You may want to use the `findNode`

function for implementing `insertNode`

.

## Coding playground

Perform the implementation inside `generic_bst.h`

(see the comments).

Test your implementation by writing code in the `main`

function from `main.c`

.

You may want to use helper functions. For example, accept a helper function that tells you how to compare the values of a concrete type. Recall that not all data types can be directly compared with regular arithmetic operators such as `==`

or `<`

.

Build a few trees of various data types to ensure your functions behave correctly when tested together. Display the trees using `printBST`

with an appropriate helper function.

Get hands-on with 1200+ tech skills courses.