How to get min and max value from a linked list using recursive function?

Question

I am started learning data structure. Currently I am learning linked list. I have crated a linked list. I want to get the minimum value and the maximum value from the list using recursive function. I can do that using loop but I want to do that recursively. I have written functions for getting minimum and maximum value. But they are returning the first element of the list.

Minimum value function:

int getMin(node *currentNode) {
  int minValue = INT_MAX;
  if (currentNode != NULL) {
    minValue = minValue < currentNode->data ? minValue : currentNode->data;
    getMin(currentNode->next);
  }
  return minValue;
}

Maximum value function:

int getMax(node *currentNode) {
  int maxValue = INT_MIN;
  if (currentNode) {
    maxValue = currentNode->data > maxValue ? currentNode->data : maxValue;
    getMax(currentNode->next);
  }
  return maxValue;
}

My full program:

#include <bits/stdc++.h>

using namespace std;

struct node {
  int data;
  node *next;
} *root;

void append(vector<int> vec) {
  node *currentNode, *tail;
  root = new node();
  root->data = vec[0];
  root->next = NULL;
  tail = root;
  for (vector<int>::iterator i = vec.begin() + 1; i < vec.end(); i++) {
    currentNode = new node();
    currentNode->data = *i;
    currentNode->next = NULL;
    tail->next = currentNode;
    tail = tail->next;
  }
}

void display(node *currentNode) {
  if (currentNode != NULL) {
    cout << currentNode->data << " ";
    display(currentNode->next);
  }
}

int getMin(node *currentNode) {
  int minValue = INT_MAX;
  if (currentNode != NULL) {
    minValue = minValue < currentNode->data ? minValue : currentNode->data;
    getMin(currentNode->next);
  }
  return minValue;
}

int getMax(node *currentNode) {
  int maxValue = INT_MIN;
  if (currentNode) {
    maxValue = currentNode->data > maxValue ? currentNode->data : maxValue;
    getMax(currentNode->next);
  }
  return maxValue;
}

int main() {
  vector<int> vec {5, 7, 3, 4, 6};
  append(vec);
  display(root);
  cout << "\nMin: " << getMin(root) << "\n";
  cout << "Max: " << getMax(root) << "\n";

  return 0;
}

I am getting the first item of the link. Why not returning the minimum and maximum value? How to fix this problem?

When you do the recursive calls to getMin and getMax, what happens with the values those calls returns? — Some programmer dude
– Some programmer dude, Commented Sep 16, 2022 at 5:58

john · Accepted Answer · 2022-09-16 06:04:22Z

1

The obvious problem is that you call your function recursively, but ignore the return value. This means that only the first item in the list is considered.

int getMin(node *currentNode) {
  int minValue = INT_MAX;
  if (currentNode != NULL) {
    minValue = minValue < currentNode->data ? minValue : currentNode->data;
    getMin(currentNode->next); // the return value here is being ignored.
  }
  return minValue;
}

Here's the correct solution

int getMin(node *currentNode) {
  if (currentNode != NULL) {
    int curr = currentNode->data;
    int rest = getMin(currentNode->next); // don't ignore the return value
    return curr < rest ? curr : rest; // which is less? the current item or
                                      // the minimum item in the rest of the list
  }
  else {
    return INT_MAX;
  }
}

answered Sep 16, 2022 at 6:04

john

88.3k5 gold badges61 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Anikul Islam Over a year ago

What an excellent solution for me it is. You solution code is speaking for itself. My concept is cleared why I was getting wrong answer by your solution. Thank you so much.

Collectives™ on Stack Overflow

How to get min and max value from a linked list using recursive function?

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related