Jan 052016
 

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

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)