Jun 112012
 

Given a Binary Search Tree (BST), where will you find the node containing minimum value in the Tree? For example: If the tree is as given below

Then answer is 1. Write a function that returns the least value in given BST.

Solution:

The minimum value in a Binary search tree is always in the left-most node. (The maximum value will be in the right-most node. If the left subtree is empty, then root stores the minimum value.

int getMinimum(Node* root)
{
    while(root->lptr != NULL)
        root = root->lptr;

    return root->data;
}

In this cases, we are assuming the Node of the tree is defined as below:

struct Node
{
    Node* lptr;  // Left Subtree
    int data;
    Node * rptr; // Right Subtree
};

Feel free to provide your feedback / comments.
————————————————————–

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)