tree = {
  ['a'] = {'x', 'xx'},
  ['b'] = {'y', 'yy'},
  ['c'] = {'z', 'zz'}
}

function deep_next(tbl, cursor, parent_struct)
  local _parent_struct = parent_struct or {}

  -- if cursor is at a not empty table, continue inside that
  if type(tbl[cursor]) == 'table' and next(tbl[cursor]) ~= nil then
    table.insert(_parent_struct {tbl, cursor})
    return tbl[cursor], next(tbl[cursor]), _parent_struct

  -- otherwise, if return next() if it is not nil
  elseif next(tbl, cursor) ~= nil then
    return next(tbl, cursor), tbl, _parent_struct

  -- if next() is nil, traverse back on parent chain
  else
    -- if any parent has a not nil next(), return that
    while #parent_struct ~= nil do
      table.remove(_parent_struct)
      local _node = _parent_struct[#_parent_struct]
      local _next = next(_node[1][_node[2]])
      if _next ~= nil then
        return _next, _node[1], _parent_struct
      end
    end

    -- otherwise return nil, iteration ends
    return nil
    end
  end
end

for k, v in deep_next(), t do
  print(k, v)
end