Interview Question: Node with minimum value in a BST

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

Then your function should return 1

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;
}

Function to get the maximum element in the tree will also be similar:

int getMaximum(Node* root)
{
    while(root->rptr != NULL)
        root = root->rptr;

    return root->data;
}

In both the 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
};

Interview Questions Archive:

         To see all the questions in the category Click Here...