How to handle flutter bottom navigation bar when back button is pressed to go to the previous route?

try this, created a custom navigation queue that hold route indexes

import 'dart:collection';

import 'package:flutter/material.dart';

class MyApp extends StatefulWidget {
  @override
  _MyAppState createState() => _MyAppState();
}

class _MyAppState extends State<MyApp> {


  ListQueue<int> _navigationQueue =ListQueue();
  int index=0;


  @override
  Widget build(BuildContext context) {

    return WillPopScope(

///this method will be called on press of the back button
      onWillPop: ()async{
     /* Use this code if you just want to go back to 0th index
         if(index == 0)
           return true;
         setState(() {
          index = 0;
        });
      return false;
    */

/* below code keeps track of all the navigated indexes*/
        if(_navigationQueue.isEmpty)
          return true;
        
        setState(() {
          index = _navigationQueue.last;
          _navigationQueue.removeLast();
        });
        return false;
      },


      child: Scaffold(
        body: (getBody(index)),


        bottomNavigationBar: BottomNavigationBar(
          backgroundColor: Colors.white,
          selectedItemColor: Color(0xFFf5851f),
          unselectedItemColor: Colors.grey,
          type: BottomNavigationBarType.fixed,

          currentIndex: index,



          // handles onTap on bottom navigation bar item
          onTap: (value) {
            _navigationQueue.addLast(index);
            setState(() => index = value);
            print(value);
          },


          items: [
            BottomNavigationBarItem(
                icon: Icon(Icons.restaurant),
                title: Text('GMA',)),
            BottomNavigationBarItem(
                icon: Icon(Icons.call),
                title: Text('CALL ON ORDER')),
            BottomNavigationBarItem(
                icon: Icon(Icons.notifications),
                title:Text('NOTIFICATION')),
            BottomNavigationBarItem(
                icon: Icon(Icons.shopping_cart),
                title: Text('CART'),),

          ],
        ),

      ),);


  }


  Widget getBody(int index) {
    switch (index) {
      case 0:
        return firstpage(); // Create this function, it should return your first page as a widget
      case 1:
        return ProductSearch(); // Create this function, it should return your second page as a widget
      case 2:
        return Account(); // Create this function, it should return your third page as a widget
      case 3:
        return Cart(); // Create this function, it should return your fourth page as a widget
    }
  }
}

@Niteesh I added some improvements to your answer so that it works in the correct way:

  // Initialize index on 0
  ListQueue<int> _navigationQueue = ListQueue();
  int _index = 0;


  // Change this section (If the queue is empty return first tab)
  onWillPop: () async {
    if (_navigationQueue.isEmpty) return true;
      setState(() {
      _navigationQueue.removeLast();
      int position = _navigationQueue.isEmpty ? 0 : _navigationQueue.last;
      _index = position;
    });
    return false;
  }

  // And this part (will remove repeated elements from the list)
  onTap: (index) {
    if(index != _index){
      _navigationQueue.removeWhere((element) => element == index);
      _navigationQueue.addLast(index);
      setState(() {
        this._index = index;
      });
    }
  },
  currentIndex: this._index,
  ...

This may help for someone. I've 2 version:

1. If you press Back Button for the first time, it navigates to initial tab's home screen and next time lefts the App:

   WillPopScope(
      onWillPop: () async {
        if (_selectedPageIndex != 0) {
        setState(() {
            _selectedPageIndex=0;
          });
          return false;
        }
        return true;
      },
      child: Scaffold(...

2. This goes back until _selectedPageIndex = 0 and than lefts the App

   WillPopScope(
      onWillPop: () async {
        if (_selectedPageIndex != 0) {
          setState(() {
            _selectedPageIndex--;
          }); 
          return false;
        }
        return true;
      },
      child: Scaffold(...

//edit: changed a line of code