run.php

<?php 

  //Main solution begins

  /**
   * The custom comparison function handed to usort
   */
  function sort_fn($a, $b)
  {
    //sort by menuText and fallback to catDesc
    if (!$a['menuText'] && !$b['menuText']) {
      return strnatcmp($a['catDesc'], $b['catDesc']);
    }
    if (!$a['menuText'] || !$b['menuText']) {
      return $a['menuText'] ? -1 : 1;
    }
    return strnatcmp($a['menuText'], $b['menuText']);
  }

  /**
   * The recursion handler
   */
  function recurse_children_sort(&$children_array)
  {
    //recurse
    foreach ($children_array as &$item) {
      if (count($item['children'])) {
        recurse_children_sort($item['children']);
      }
    }
    //sort
    usort($children_array, 'sort_fn');
  }

  /**
   * The main/entry function
   */
  function sort_data($jsonstring)
  {
    $jsonstring = json_encode($jsonstring); //for testing with data in decoded format
    $data = json_decode($jsonstring, true);

    //loop through items
    foreach ($data as &$item) {
      //start the real thing
      recurse_children_sort($item['categories']['children']);
    }

    return $data;
    // dd($data);
  }

  //Main solution ends 


//test data
  $data = [
    [
      "categories" => [
        "catDesc" => 'pd1',
        "keyNote" => "None",
        "menuText" => 'p1',
        "children" => [
          [
            "catDesc" => 'ppd1',
            "keyNote" => "None",
            "menuText" => 'pp1',
            "children" => [
              [
                "catDesc" => 'pppd2',
                "keyNote" => "None",
                "menuText" => 'ppp2',
                "children" => [
                  [
                    "catDesc" => 'ppppd2',
                    "keyNote" => "None",
                    "menuText" => 'pppp2',
                    "children" => [],
                  ],
                  [
                    "catDesc" => 'ppppd1',
                    "keyNote" => "None",
                    "menuText" => 'pppp1',
                    "children" => [],
                  ],
                ],
              ],
              [
                "catDesc" => 'pppd1',
                "keyNote" => "None",
                "menuText" => 'ppp1',
                "children" => [
                  [
                    "catDesc" => 'ppppd2',
                    "keyNote" => "Case with some menuText missing, 4/4",
                    "menuText" => '',
                    "children" => [],
                  ],
                  [
                    "catDesc" => 'ppppd1',
                    "keyNote" => "Case with some menuText missing, 3/4",
                    "menuText" => '',
                    "children" => [],
                  ],
                  [
                    "catDesc" => 'ppppd4',
                    "keyNote" => "Case with some menuText missing, 2/4",
                    "menuText" => 'pppp4',
                    "children" => [],
                  ],
                  [
                    "catDesc" => 'ppppd3',
                    "keyNote" => "Case with some menuText missing, 1/4",
                    "menuText" => 'pppp3',
                    "children" => [],
                  ],
                ],
              ],
            ],
          ],
          [
            "catDesc" => 'ppd4',
            "keyNote" => "None",
            "menuText" => 'pp4',
            "children" => [],
          ],
          [

            "catDesc" => 'ppd2',
            "keyNote" => "None",
            "menuText" => 'pp2',
            "children" => [],
          ],
          [

            "catDesc" => 'ppd3',
            "keyNote" => "None",
            "menuText" => 'pp3',
            "children" => [],
          ],
        ],
      ]
    ],
    [
      "categories" => [
        "catDesc" => 'pd2',
        "keyNote" => "None",
        "menuText" => 'p2',
        "children" => [
          [
            "catDesc" => 'ppd1',
            "keyNote" => "None",
            "menuText" => 'pp1',
            "children" => [
              [
                "catDesc" => 'pppd2',
                "keyNote" => "None",
                "menuText" => 'ppp2',
                "children" => [
                  [
                    "catDesc" => 'ppppd2',
                    "keyNote" => "None",
                    "menuText" => 'pppp2',
                    "children" => [],
                  ],
                  [
                    "catDesc" => 'ppppd1',
                    "keyNote" => "None",
                    "menuText" => 'pppp1',
                    "children" => [],
                  ],
                ],
              ],
              [
                "catDesc" => 'pppd1',
                "keyNote" => "None",
                "menuText" => 'ppp1',
                "children" => [],
              ],
            ],
          ],
          [
            "catDesc" => 'ppd4',
            "keyNote" => "None",
            "menuText" => 'pp4',
            "children" => [],
          ],
          [

            "catDesc" => 'ppd2',
            "keyNote" => "None",
            "menuText" => 'pp2',
            "children" => [],
          ],
          [

            "catDesc" => 'ppd3',
            "keyNote" => "None",
            "menuText" => 'pp3',
            "children" => [],
          ],
        ],
      ]
    ],
  ];







  print_r(sort_data($data));
  //dd(sort_data($data));