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, Sep 16 '22 at 05:58
Also: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Sep 16 '22 at 05:59

score 1 · Accepted Answer · answered Sep 16 '22 at 06:04

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

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. — Anikul Islam, Sep 16 '22 at 06:13

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

1 Answers1