Question

Research the topic of binary search trees. Write a brief summary of your understanding of this. Design a simple program, using pseudocode, that performs a search of a binary search tree.. In your own words, explain how a binary search tree works using graph theory terminology. Construct a binary search tree for any alphabetically ordered list of five words. Represent it visually as a graph. Discuss any characteristics you note about the graph you created in part (d). In your discussion, make sure to address the following: What are the degrees of each vertex? Is it a complete graph? Is the graph planar?

Answer 1

Binary Search Tree is a node-based binary tree data structure which has the following properties:

· The left subtree of a node contains only nodes with keys lesser than the node’s key.

· The right subtree of a node contains only nodes with keys greater than the node’s key.

· The left and right subtree each must also be a binary search tree.

               

Pseudo code(algorithm)

If root == NULL

    return NULL;

If number == root->data

    return root->data;

If number < root->data

    return search(root->left)

If number > root->data

    return search(root->right)

Explanation in words

4 is not found so, traverse through the left subtree of 8

4 is not found so, traverse through the right subtree of 3

4 is not found so, traverse through the left subtree of 6 And then it found after 6

If the value is found, we return the value so that it gets propagated in each recursion step as shown in the image below.

If you might have noticed, we have called return search(struct node*) four times. When we return either the new node or NULL, the value gets returned again and again until search(root) returns the final result.

If the value is not found, we eventually reach the left or right child of a leaf node which is NULL and it gets propagated and returned.

Degrees of each vertex

Complete graph

Planar graph