1 We are asked to add a function Position lowestKeyconst Pos

1) We are asked to add a function Position lowestKey(const Position& v) const to the class SearchTree.

Function prototype: Position lowestKey(const Position& v);

input argument: position of the starting node in the binary search tree to calculate from. For the whole tree this would be the position for the root of the tree.

return value: position of the node having the lowest key value.

i. Describe strategy with reasonings and examples to convince that it will work.

ii. Implement the function using C++ and show the source code listing.

Solution

Let us keep the approach very simple we just traverse the node from root node to left recursively until left node is NULL.The node whose left is NULL is the node with minimum value.Here in the following code we also describe a test case and input values such as 10,18,7,9,17. And the result is the minimum value & is provided to us as output

             Time Complexity of the given function in Worst case and average case is O(n)

#include <stdio.h> /*This code is basically in C programming as it is easy to understand and approach is simple in order to convert into c++ just change the basic syntax*/

#include<stdlib.h>

/* A binary tree basic structure */

struct node

{

    int value;

    struct node* lchild;

   struct node* rchild;

};

/* Given function defined a fresh node with data and null is allocated to left and right child. */

struct node* newNode(int value)

{

struct node* node = (struct node*)

                       malloc(sizeof(struct node));

node->data = value;

node->left = NULL;

node->right = NULL;

  

return(node);

}

/*

There Give a binary search tree and a value,

inserts a new node with the given value in

the correct place in the tree. Returns the new

root pointer which the caller should then use

*/

struct node* insert(struct node* node, int data)

{

/* 1. If the tree is empty, return a new,    

      single node */

if (node == NULL)

    return(newNode(value));

else

{

    /* 2. Otherwise, recur down the tree */

    if (value <= node->value)

        node->lchild = insert(node->lchild, value);

    else

        node->rchild = insert(node->rchild, value);

  

    /* return the (unchanged) node pointer */

    return node;

}

}

/* Given a non-empty binary search tree,

return the minimum of the binary tree and need not to search the whole tree

. */

int PositionLowestKey(struct node* node) {

struct node* current = node;

/* loop down to find the leftmost leaf of the tree*/

while (current->lchild != NULL) {

    current = current->lchild;

}

return(current->value);

}

/* main program to test the function*/  

int main()

{

struct node* root = NULL;

root = insert(root, 4);

insert(root, 10);

insert(root, 18);

insert(root, 7);

insert(root, 9);

insert(root, 17);

printf(\"\ Minimum value in BST is %d\", PositionLowestValue(root));

getchar();

return 0;   

}