Course list Register Sign in

Information

Author(s) Jérôme Mayolet Anthony Doeraene
Deadline No deadline
Submission limit No limitation

Tags

Sign in

Sign in

Binary Search Tree

Using the structure node described as below :

struct node {
    struct node *left, *right;
    int value;
};

Here's an exemple of a tree generated by this structure:

https://inginious.org/admin/uclouvain-lepl1503/edit/task/Binary_search_tree/files?action=download&path=/student/arbre.JPG

You have to create a tree by calling the function add repetitively. The function search must check efficiently if the tree contains a certain value.

We will use a binary ordered tree, with all nodes at right having their value greater the the value of root node, and the nodes at left will have their value less than the one of root node. If a value is already contained in the tree, you shouldn't add any new node.

Example of the behaviour when calling add:

https://inginious.org/admin/uclouvain-lepl1503/edit/task/Binary_search_tree/files?action=download&path=/student/sequence%20ajout.JPG
Question 1: Search

Write the function to search efficiently a value in a tree

/**
* This function check if "value" is contained in the tree
* @param root  : the root node of the tree (perhaps NULL)
* @param value : the value to search in the tree
* @return 1 if "value" is in the tree , 0 otherwise
*/
int search(struct node *root, int value);
Question 2: Add

Write the function to insert correctly a value to the tree

/**
* This function add a node with a value of "value" in the tree.
* If this value is already contained in the tree, nothing is done.
*
* @param root the root of the tree (perhaps NULL)
* @param value the value to insert in the tree
* @return root of the tree
*         NULL if malloc fails
*/
struct node *add(struct node *root, int value);