Prisoners and the lightbulb puzzle
September 28, 2015
Compare to strings given as linked list
February 18, 2016

Find minimum and maximum value in a tree

Given a Binary tree (not BST), write code to find the minimum and maximum value in the tree.
Binary TreeFor example, if the tree is as shown in the picture, then the output should be:

Minimum: 2
Maximum: 20


Solution:

It is a very simple problem, where we traverse the entire tree and keep track of the minimum value found till now. For each node we will compare it against the minimum till now. If the value at node is less than that then we will update the minimum with current node.
Tree can be traversed in any order (pre, post, etc.). Below is the complete program (with helper functions) for same:
Code

#include <iostream>
using namespace std;
struct Node{
    Node* lptr;
    Node* rptr;
    int data;
    Node(int value):lptr(NULL),rptr(NULL),data(value){}
};
Node* findMinimum(Node* r)
{
    if(r==NULL) { return NULL; }
    // Leaf Node. Hence it is the minimum.
    if(r->lptr == NULL && r->rptr == NULL) { return r; }
    Node* temp1 = findMinimum(r->lptr);
    Node* temp2 = findMinimum(r->rptr);
    Node* minNode = r;
    if(temp1 != NULL && temp1->data < minNode->data)
        minNode = temp1;
    if(temp2 != NULL && temp2->data < minNode->data)
        minNode = temp2;
    return minNode;
}
Node* findMaximum(Node* r)
{
    if(r==NULL) { return NULL; }
    // Leaf Node. Hence it is the minimum.
    if(r->lptr == NULL && r->rptr == NULL) { return r; }
    Node* temp1 = findMaximum(r->lptr);
    Node* temp2 = findMaximum(r->rptr);
    Node* maxNode = r;
    if(temp1 != NULL && temp1->data > maxNode->data)
        maxNode = temp1;
    if(temp2 != NULL && temp2->data > maxNode->data)
        maxNode = temp2;
    return maxNode;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    Node* r = new Node(5);
    r->lptr = new Node(6);
    r->lptr->lptr = new Node(8);
    r->lptr->rptr = new Node(9);
    r->rptr = new Node(4);
    r->rptr->rptr = new Node(20);
    r->rptr->lptr = new Node(2);
    cout<<"Minimum :"<<findMinimum(r)->data<<endl;
    cout<<"Maximum :"<<findMaximum(r)->data<<endl;
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *